**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.

## Abstract

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