Explicit lower bound of 4.5n - o(n) for Boolean circuits
Oded Lachish, Ran Raz · 2001
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 fand; org gates needed to compute a certain Boolean function, over the basis fand; or; notg (where the not gates are not counted). Our proof is based on a new combinatorial property of Boolean functions, called StronglyTwo -Dependence, a notion that may be interesting in its own right. Our lower bound applies to any Strongly-TwoDependent Boolean function.