Authors: Richard Beigel, Nick Reingold, and Daniel Spielman
Abstract: We show that every AC0 predicate is computed by a low-degree probabilistic polynomial over the reals. We show that circuits composed of a symmetric gate at the root with AND-OR subcircuits of constant depth can be simulated by probabilistic depth-2 circuits with essentially the same symmetric gate at the root and AND gates of small fanin at the bottom. In particular, every language recognized by a depth-d AC0 circuit is decidable by a probabilistic perceptron of size 2O(log4dn) and order O(log4dn) that uses O(log3n) probabilistic bits. As a corollary, we present a new proof that depth-d AND-OR circuits computing the parity of n binary inputs require size 2nΩ(1/d).
Download Full Paper