Notes of Raghu Meka’s talk

Pseudorandom generators for combinatorial shapes

Is {RL=L} ?

Saks-Zhou: {RL \subset SPACE((\log n)^{2/3})}.

There are a number of PRGs fooling observers with low space resources.

1. Combinatorial shapes

Fooling linear forms amounts to finding a small number {k} of Boolean variables whose sum is close from being binomially {\mathcal{B}(n,\frac{1}{2})} distributed, with {n\gg k}.

Combinatorial rectangles are {[m]}-valued functions on {[m]^n}, which are ANDs of characteristic functions of subsets in {[m]`}

Definition 1 An {(m,n)}-combinatorial shape is a Boolean function on {[m]^n} of the form {h(} characteristic functions of subsets{)}, where {h} is a symmetric Boolean function.

This class contains half-spaces (see Gopalan’s talk).

Question: Can we find PRGs which fool combinatorial shapes ?

1.1. Result

Theorem 2 We construct a pseudorandom generator of seed length

\displaystyle  \begin{array}{rcl}  O(\log n +\log m +(\log\frac{1}{\epsilon})^2). \end{array}

which {\epsilon}-fools {(m,n)}-combinatorial shapes.

2. Proof

2.1. {m=2}

This amounts to fooling linear forms in total variation. Do this recursively. If {X} is binomial (or close to it in total variation) and {Y} is close to binomial in {CDF} distance, then {X+Y} is close to binomial in total variation (Convolution Lemma). Do the partitioning into {X+Y} randomly.

{CDF} distance is {L_{\infty}} norm of difference of cumulative distribution functions.

2.2. General case

Reduce from combinatorial shapes to combinatorial sums: every {h(} 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 {k}-wise independence, {k=22}.

3. Discrete CLT

This deals with convergence of sums of random variables to binomial distribution.

Theorem 3 Let {Y_i} be independent Boolean random variables, and {Z_j} independent Bernoulli variables. Then {Y=\sum_{i}Y_i} and {Z=\sum_{j}Z_j} are close in total variation,

\displaystyle  \begin{array}{rcl}  dist_{TV}(\sum_{i}Y_i ,\sum_{j}Z_j )\leq O(\frac{1}{\sqrt{\sigma(Y)}}). \end{array}

Proof relies again on Convolution Lemma.

4. Open questions

Optimal dependence on error rate ?

Better use of symmetry ?


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s