## 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 ?