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 language | English (US) |
---|---|
Pages (from-to) | 399-408 |
Number of pages | 10 |
Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
State | Published - Sep 29 2001 |
Externally published | Yes |
Event | 33rd Annual ACM Symposium on Theory of Computing - Creta, Greece Duration: Jul 6 2001 → Jul 8 2001 |
All Science Journal Classification (ASJC) codes
- Software