Blog Archives

Combinatorial Design and Pseudorandom Generator

For a set of size \(l\), choose \(m\) subsets each of size \(n\) such that each pair of subsets has intersection size at most \(d\). This gives a combinatorial design with parameters \((m,l,n,d)\). That is, we have \(I_1,\ldots, I_m \subseteq

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