Name
Abstract | ||
|---|---|---|
The following size--depth tradeoff for threshold circuits is obtained: any threshold circuit of depth $d$ that computes the parity function on $n$ variables must have at least $n^{1 + c\theta^{-d }}$ edges, where $c0$ and $\theta \leq 3$ are constants independent of $n$ and $d$. Previously known constructions show that up to the choice of $c$ and $\theta$ this bound is best possible. In particular, the lower bound implies an affirmative answer to the conjecture of Paturi and Saks that a bounded-depth threshold circuit that computes parity requires a superlinear number of edges. This is the first superlinear lower bound for an explicit function that holds for any fixed depth and the first that applies to threshold circuits with unrestricted weights. The tradeoff is obtained as a consequence of a general restriction theorem for threshold circuits with a small number of edges: For any threshold circuit with $n$ inputs, depth $d$, and at most $kn$ edges, there exists a partial assignment to the inputs that fixes the output of the circuit to a constant while leaving $\lfloor n/(c_1k)^{c_2\theta^{d}} \rfloor$ variables unfixed, where $c_1,c_2 0$ and $ \theta \leq 3$ are constants independent of $n$, $k$, and $d$.A tradeoff between the number of gates and depth is also proved: any threshold circuit of depth $d$ that computes the parity of $n$ variables has at least $(n/2)^{1/2(d-1)}$ gates. This tradeoff, which is essentially the best possible, was proved previously (with a better constant in the exponent) for the case of threshold circuits with polynomially bounded weights in [K. Siu, V. Roychowdury, and T. Kailath, IEEE Trans. Inform. Theory, 40 (1994), pp. 455--466]; the result in the present paper holds for unrestricted weights. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1137/S0097539792282965 | SIAM J. Comput. |
Keywords | Field | DocType |
superlinear number,threshold circuits,explicit function,parity function,depth tradeoff,unrestricted weight,fixed depth,threshold circuit,small number,computes parity,bounded-depth threshold circuit,depth tradeoffs,circuit complexity | Discrete mathematics,Combinatorics,Circuit complexity,Exponent,Upper and lower bounds,Parity function,Implicit function,Parity (mathematics),Conjecture,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
26 | 3 | 0097-5397 |
Citations | PageRank | References |
32 | 1.89 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Russell Impagliazzo | 1 | 5444 | 482.13 |
| Ramamohan Paturi | 2 | 1260 | 92.20 |
| Michael Saks | 3 | 2595 | 302.11 |