Explicit lower bound of 4.5n - o(n) for Boolean circuits

O. Lachish, R. Raz

Research output: Contribution to journalConference article

36 Scopus citations

Abstract

We prove a lower bound of 4.5n - o(n) for the circuit complexity of an explicit Boolean function (that is, a function constructible in deterministic polynomial time), over the basis U2. That is, we obtain a lower bound of 4.5n - o(n) for the number of {and, or} gates needed to compute a certain Boolean function, over the basis {and, or, not} (where the not gates are not counted). Our proof is based on a new combinatorial property of Boolean functions, called Strongly-Two-Dependence, a notion that may be interesting in its own right. Our lower bound applies to any Strongly-Two-Dependent Boolean function.

Original languageEnglish (US)
Pages (from-to)399-408
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Sep 29 2001
Externally publishedYes
Event33rd Annual ACM Symposium on Theory of Computing - Creta, Greece
Duration: Jul 6 2001Jul 8 2001

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Explicit lower bound of 4.5n - o(n) for Boolean circuits'. Together they form a unique fingerprint.

  • Cite this