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