Favorite Theorems: Limited Independence

When can limited randomness act as well as true random bits?

Polylogarithmic independence fools AC⁰ circuits by Mark Braverman (JACM 2010)

To explain this result consider choosing uniformly from among the following four strings:

000 110 101 011

If we look at any two of the bits, say the first and third, all four possibilities 00 10 11 01 occur. The sequence is thus 2-wise independent. We can get 2-wise independence using only two random bits to choose one of the four strings. In general one can get k-wise independent in n-bit strings using O(k² log n) random bits.

Braverman shows that any polylogarithmic independent distribution fools polynomial-size constant-depth circuits (AC⁰), or more precisely for a size s depth d circuit C, for k=(log (m/ε))^O(d2), the probability that C will output 1 with uniformly-random inputs will differ at most ε from the probability C outputs 1 from inputs chosen from a k-wise random distribution. Braverman's result followed after Bazzi and Razborov proved a similar result for depth-2 circuits (CNF formulas).

Another nice result along these lines: Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola show that Bounded Independence Fools Halfspaces. A half-space is just a weighted threshold function (is the sum of w_ix_i at most some given θ). Diakonikolas et al. show that one can fool halfspaces with k=O(ε^-2log²(1/ε)), in particular for constant ε, k is a constant independent of the number of variables.