**Authors:**
Richard Beigel,
Nick Reingold, and
Daniel A. Spielman.
**Bibliographic Information:**
First appeared in the
*Proceedings of the 23rd Annual ACM Symposium on the
Theory of Computing,* 1991, pp. 1-9.
Will appear soon in the
*Journal of Computer and System Sciences*.

## Abstract

In his seminal paper on probabilistic Turing machines,
Gill asked whether the class $\PP$ is closed
under intersection and union. We give a positive answer to this
question. We also show that $\PP$ is closed under a variety of
polynomial-time truth-table reductions. Consequences in
complexity theory include the definite collapse and
(assuming $\P \neq \PP $)
separation of certain query hierarchies over $\PP$.
Similar techniques allow us to combine several threshold gates
into a single threshold gate. Consequences in the study of
circuits include the simulation of circuits with a small number
of threshold gates by circuits having only a single threshold
gate at the root (perceptrons), and a lower bound on the number
of threshold gates needed to compute the parity
function.

To view the paper, click here.
To download a compressed version, click here.

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