Size-depth trade-offs for threshold circuits

Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

The following size-depth trade- off for threshold circuits is obtained: Any threshold circuit of depth d that computes the parity function on n variables must have at least n1+cθ-d edges, where constants c > 0 and θ < 3 are constants independent of n and d. Previously known constructions show that up to the choice of c and θ 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 super-linear number of edges. This is the first super-linear lower bound for an explicit function that holds for any fixed depth, and the first that applies to threshold circuits with unrestricted weights. The trade-off 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 len edges, there exists a partial assignment to the inputs that fixes the output of the circuit to a constant, while leaving [n/(c1k)C2θd J variables unfixed, where ci,c2 > 0 and 0 < 3 are constants independent of n,k, and d. A trade-off 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 trade-off, which is essentially the best possible, was proved previously (with a better constant) for the case of threshold circuits with polynomially bounded weights in (22); the result in the present paper holds for unrestricted weights.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993
PublisherAssociation for Computing Machinery
Pages541-550
Number of pages10
ISBN (Electronic)0897915917
DOIs
StatePublished - Jun 1 1993
Event25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States
Duration: May 16 1993May 18 1993

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129585
ISSN (Print)0737-8017

Other

Other25th Annual ACM Symposium on Theory of Computing, STOC 1993
Country/TerritoryUnited States
CitySan Diego
Period5/16/935/18/93

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Size-depth trade-offs for threshold circuits'. Together they form a unique fingerprint.

Cite this