Exponential lower bounds for depth 3 boolean circuits

Ramamohan Paturi, Michael E. Saks, Francis Zane

Research output: Contribution to journalConference articlepeer-review

7 Scopus citations

Abstract

We consider the class Σ3k of unbounded fan-in depth-3 boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has Ω(2εn/k) gates (for k = O(n1/2)) for some ε>0, and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC1 that requires 2n-o(n) size depth 3 circuits. The main tool is a theorem that shows that any Σ32 circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form xi = 0, xi = 1, xi = xj or xi = x̄j) of dimension at least log(a/s)/log n.

Original languageEnglish (US)
Pages (from-to)86-91
Number of pages6
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Exponential lower bounds for depth 3 boolean circuits'. Together they form a unique fingerprint.

Cite this