I will discuss recent progress in the study of the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between the uniform distribution over any good error correcting code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That is, such distributions are very far from each other. We strengthen their result, and show that the distance is in fact exponentially close to one. This allows us to strengthen the parameters in their application for lower bounds for succinct data structures for codes.

From a technical point of view, we develop new large deviations bounds for functions computed by collections of small depth decision trees, which we then apply to obtain bounds for AC0 circuits via the Switching Lemma. We show that if such functions are Lipschitz on average in a certain sense, then they are in fact Lipschitz almost everywhere. This type of result falls into the extensive line of research which studies large deviations bounds for the sum of random variables which, while not independent, exhibit bounds similar to those obtained by independent random variables.

Joint work with Russell Impagliazzo (IAS and UCSD) and Shachar Lovett (IAS and UCSD).