Abstract
The current best lower bound of 4.5n − o(n) for an explicit family of Boolean circuits [3] is improved to 5n − o(n) using the same family of Boolean function.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Blum. A 2.75n-lower bound on the network complexity of boolean functions. Tech. Rept. A 81/05, Universität des Saarlandes, 1981.
N. Blum. A Boolean function requiring 3n network size. Theoret. Comput. Sci., 28, pp. 337–345, 1984.
O. Lachish and R. Raz. Explicit lower bound of 4.5n − o(n) for Boolean circuits. Proc. STOC’01, pp. 399–408, 2001.
W. Paul. A 2.5n-lower bound on the combinational complexity of boolean functions. SIAM J. Comput. 6, pp. 427–443, 1977.
C. Schnorr. Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen. Computing 13, pp. 155–171, 1974.
L. Stockmeyer. On the combinational complexity of certain symmetric Boolean functions. Math. System Theory 10, pp. 323–336, 1977.
I. Wegener. Branching programs and binary decision diagrams. SIAM Monographs on Discrete Mathematics and Applications, 1999.
U. Zwick. A 4n lower bound on the combinatorial complexity of certain symmetric Boolean functions over the basis of unate dyadic Boolean functions. SIAM J. Comput. 20, pp. 499–505, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Iwama, K., Morizumi, H. (2002). An Explicit Lower Bound of 5n − o(n) for Boolean Circuits. In: Diks, K., Rytter, W. (eds) Mathematical Foundations of Computer Science 2002. MFCS 2002. Lecture Notes in Computer Science, vol 2420. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45687-2_29
Download citation
DOI: https://doi.org/10.1007/3-540-45687-2_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44040-6
Online ISBN: 978-3-540-45687-2
eBook Packages: Springer Book Archive