Blog Archives

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