Bounded-Depth Circuits Cannot Sample Good Codes
Shachar Lovett, Emanuele Viola · Computational Complexity · 2011
We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a. AC0) circuit, and (ii) the uniform distribution over any code that is ``good'', i.e. has constant relative distance and rate. This seems to be the first lower bound of this kind. We give two simple applications of this result: (1) any data structure for storing codewords of a good code requires an additive logarithmic redundancy, if each bit of the codeword can be retrieved by a small AC0 circuit; (2) for some choice of the underlying combinatorial designs, the output distribution of Nisan's pseudorandom generator against AC0 circuits of depth d cannot be sampled by small AC0 circuits of depth less than d.