# Parity, circuits, and the polynomial-time hierarchy

@article{Furst2005ParityCA, title={Parity, circuits, and the polynomial-time hierarchy}, author={Merrick L. Furst and James B. Saxe and Michael Sipser}, journal={Mathematical systems theory}, year={2005}, volume={17}, pages={13-27} }

A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function. Introducing the notion of polynomial-size, constant-depth reduction, similar results are shown for the majority, multiplication, and transitive closure functions. Connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy.

#### 217 Citations

On the Correlation Between Parity and Modular Polynomials

- Mathematics, Computer Science
- Theory of Computing Systems
- 2011

We consider the problem of bounding the correlation between parity and modular polynomials over ℤq, for arbitrary odd integer q≥3. We prove exponentially small upper bounds for classes of polynomials… Expand

Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates

- Mathematics, Computer Science
- COCOON
- 2007

In the quasi-polynomial size setting, this work provides an exact characterization of the class of symmetric functions in terms of their balance, and proves strong (up to exponential) size lower bounds for such circuits computing symmetric Boolean functions. Expand

The correlation between parity and quadratic polynomials mod 3

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 2004

It is proved that in order to compute parity, circuits consisting of a threshold gate at the top, mod 3 gates in the middle, and AND gates of fan-in two at the inputs must be of size 2Ω(n). Expand

On the Correlation Between Parity and Modular Polynomials

- Mathematics, Computer Science
- MFCS
- 2006

We consider the problem of bounding the correlation between parity and modular polynomials over ℤq, for arbitrary odd integer q ≥3. We prove exponentially small upper bounds for classes of… Expand

Circuits constructed with MODq gates cannot compute “AND” in sublinear size

- Mathematics, Computer Science
- computational complexity
- 2005

Algebraic techniques are used to prove that any circuit constructed with MODq gates that computes the AND function must use Ω(n) gates at the first level. The best bound previously known to be valid… Expand

On the power of small-depth threshold circuits

- Mathematics, Computer Science
- computational complexity
- 2005

It is proved that there are monotone functionsfk that can be computed in depthk and linear size ⋎, ⋏-circuits but require exponential size to compute by a depthk−1 monot one weighted threshold circuit. Expand

Techniques for analyzing the computational power of constant -depth circuits and space -bounded computation

- Computer Science
- 2006

An O(log n log log n) upper bound is proved on the space complexity of undirected st-connectivity and a new expression for the exponential sum is shown which involves a certain affine space corresponding to the polynomial. Expand

Upper and lower bounds for some depth-3 circuit classes

- Computer Science, Mathematics
- computational complexity
- 2005

It is shown that the fan-in of the AND gates can be reduced toO(logn) in the case wherem is unbounded, and to a constant in the cases where m is constant, and an exponential lower bound is proved if OR gates are also permitted on level two andm is a constant prime power. Expand

Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth

- Computer Science, Mathematics
- LICS
- 2018

This paper builds on Immerman's characterization of constant-depth polynomial-size circuits by formulae of first-order logic and augment the logical language with an operator for defining relations in an inductive way to obtain uniform characterizations of the Boolean classes NC1, SAC1 and AC1. Expand

Circuit complexity of linear functions: gate elimination and feeble security

- Mathematics
- 2013

In this paper, we consider provably secure cryptographic constructions in the context of circuit complexity. Based on the ideas of provably secure trapdoor functions developed in (Hirsch, Nikolenko,… Expand

#### References

SHOWING 1-10 OF 28 REFERENCES

Parity, circuits, and the polynomial-time hierarchy

- Mathematics, Computer Science
- 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981)
- 1981

A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function and connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy. Expand

On Counting Problems and the Polynomial-Time Hierarchy

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1980

The main result is that there exists an oracle set A such that PPA −(Π2P,A ∪ σ2 P,A) ≠ ∅, with the corollary that also D ≠PA − (Π 2P, a ∪σ2 p, A) ≦ ∅. Expand

The Polynomial-Time Hierarchy

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1976

The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established. Expand

Complexity of the realization of a linear function in the class of II-circuits

- Mathematics
- 1971

AbstractIt is proved that the linear function gn(x1,..., xn) = x1 + ... + xnmod 2 is realized in the class of II-circuits with complexity Lπ(gn) ≥n2. Combination of this result with S. V.… Expand

A 2.5 n-lower bound on the combinational complexity of Boolean functions

- Mathematics, Computer Science
- STOC
- 1975

A new Method for proving linear lower bounds of size 2n is presented and a trade-off result between circuit complexity and formula size is derived. Expand

A complexity theory based on Boolean algebra

- Mathematics, Computer Science
- 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981)
- 1981

It is shown that much of what is of everyday relevance in Turing-machine-based complexity theory can be replicated easily and naturally in this elementary framework. Expand

Method of determining lower bounds for the complexity of P-schemes

- Mathematics
- 1971

A method of calculating lower bounds, quadratic in the arguments of the function, for the complexity of P-schemes.

A second step toward the polynomial hierarchy

- Computer Science, Mathematics
- 17th Annual Symposium on Foundations of Computer Science (sfcs 1976)
- 1976

The principal result is that there exists a recursive oracle for which the relativized polynomial hierarchy exists through the second level; that is, there is a recursive set B such that Σ2P,B ≠ π2 P,B. Expand

Relativization of questions about log space computability

- Mathematics, Computer Science
- Mathematical systems theory
- 2005

A notion of log space Turing reducibility is introduced and it is shown that there exists a computable setA such that and. Expand

A 3n-Lower Bound on the Network Complexity of Boolean Functions

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1980

C ( f n ) is the minimal size of a Boolean network which computes f n over the base of all 16 binary Boolean operations, and this lower bound corresponds to an upper bound of 3 n provided that the authors count only those gates that depend on some variable z j. Expand