The Perceptron Strikes Back

Authors: Richard Beigel, Nick Reingold, and Daniel A. Spielman.

Bibliographic Information: In Proceedings of the 6th Annual IEEE Conference on Structure in Complexity Theory, 1991, pp. 286-291.


We show that every ${\rm AC}^{0}$ 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$ ${\rm AC}^{0}$ circuit is decidable by a probabilistic perceptron of size $2^{\O{\log^{4d}n}}$ and order $\O{\log^{4d}n}$ that uses $\O{\log^{3}n}$ 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 $2^{n^{\Omega(1/d)}}$.
To view the paper, click here.

To view a compressed version, click here.

Daniel A. Spielman
Last modified: Fri Aug 3 02:13:37 EDT 2001