**Pseudorandom generators for combinatorial shapes**

Is ?

**Saks-Zhou**: .

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 ?

** 1.1. Result **

**Theorem 2** * We construct a pseudorandom generator of seed length
*

*
** which -fools -combinatorial shapes. *

**2. Proof **

** 2.1. **

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 ?

### Like this:

Like Loading...

*Related*

## 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
http://www.math.ens.fr/metric2011/