TY - JOUR
T1 - Explicit lower bound of 4.5n - o(n) for Boolean circuits
AU - Lachish, O.
AU - Raz, R.
N1 - Funding Information:
Research supported by US-Israel BSF grant 98-00349. Research supported by US-Israel BSF grant 98-00349, and NSF grant CCR-9987077
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0034830275&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034830275&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:0034830275
SN - 0734-9025
SP - 399
EP - 408
JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing
JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing
T2 - 33rd Annual ACM Symposium on Theory of Computing
Y2 - 6 July 2001 through 8 July 2001
ER -