Pseudorandom generators for combinatorial shapes
There are a number of PRGs fooling observers with low space resources.
1. Combinatorial shapes
Fooling linear forms amounts to finding a small number of Boolean variables whose sum is close from being binomially distributed, with .
Combinatorial rectangles are -valued functions on , which are ANDs of characteristic functions of subsets in
Definition 1 An -combinatorial shape is a Boolean function on of the form characteristic functions of subsets, where is a symmetric Boolean function.
This class contains half-spaces (see Gopalan’s talk).
Question: Can we find PRGs which fool combinatorial shapes ?
Theorem 2 We construct a pseudorandom generator of seed length
which -fools -combinatorial shapes.
This amounts to fooling linear forms in total variation. Do this recursively. If is binomial (or close to it in total variation) and is close to binomial in distance, then is close to binomial in total variation (Convolution Lemma). Do the partitioning into randomly.
distance is norm of difference of cumulative distribution functions.
2.2. General case
Reduce from combinatorial shapes to combinatorial sums: every characteristic functions of subsets is close in total variation to a sum of characteristic functions of subsets. Combinatorial sums with low/high variance get treated differently. Low variance combinatorial sums are merely fooled by -wise independence, .
3. Discrete CLT
This deals with convergence of sums of random variables to binomial distribution.
Theorem 3 Let be independent Boolean random variables, and independent Bernoulli variables. Then and are close in total variation,
Proof relies again on Convolution Lemma.
4. Open questions
Optimal dependence on error rate ?
Better use of symmetry ?