## Pairwise Independence

A collection of random variables is pairwise independent if every pair of variables are independent. Given $$k$$ independent bits, we define $$n = 2^k-1$$ random variables each of which is a parity of a non-empty subset of the $$k$$ bits.

Tagged with: , , ,
Posted in Theory

## Pseudorandom Generators and Derandomization

Definition of Pseudorandom Generators Two distributions $$X$$ and $$Y$$ over $$\{0,1\}^n$$ are $$(s, \epsilon)$$-indistinguishable if, for any circuit $$C$$ of size at most $$s$$, $\left| \Pr_X[C(X) = 1] – \Pr_Y[C(Y) = 1] \right| \leq \epsilon.$ A pseudorandom generator

Tagged with: , ,
Posted in Theory