All Questions
Tagged with derandomization pr.probability
5 questions
4
votes
0
answers
164
views
Concentration Bounds for Dependent Rounding
Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$:
At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
- 271
10
votes
4
answers
509
views
Constructions better than a random one.
I am interested in examples of constructions in the complexity theory which are better than a random constructions.
The only one example of such construction which I know is in the field of error-...
11
votes
1
answer
479
views
Borel-Cantelli Lemma and Derandomization
I was reading a paper titled Random Oracles with(out) Programmability. The last paragraph of section 2.3 reads:
[Using our novel approach] there is no
need to apply well-known classical ...
- 16.6k
13
votes
2
answers
596
views
Pairwise independent gaussians
Given $X_1,\ldots,X_k$ (i.i.d. gaussians with mean $0$ and variance $1$), is it possible (how?) to sample (for $m=k^2$) $Y_1, \ldots, Y_m$ such that
$Y_i$'s are pairwise independent gaussians with ...
Anindya De
16
votes
3
answers
3k
views
Chernoff-type Inequality for pair-wise independent random variables
Chernoff-type inequalities are used to show that the probability that a sum of independent random variables deviates significantly from its expected value is exponentially small in the expected value ...
- 161