A better-than-3n lower bound for the circuit complexity of an explicit function

Published

December 15, 2016

Author(s)

Magnus G. Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov

Abstract

We consider Boolean circuits over the full binary basis. We prove a $(3+\frac{1}{86})n-o(n)$ lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser. This improves the $3n-o(n)$ bound of Norbert Blum (1984). The proof is based on the gate elimination technique extended with the following three ideas. We generalize the computational model by allowing circuits to contain cycles, this in turn allows us to perform affine substitutions. We use a carefully chosen circuit complexity measure to track the progress of the gate elimination process. Finally, we use quadratic substitutions that may be viewed as delayed affine substitutions.

Conference Dates

October 9-11, 2016

Conference Location

New Brunswick, NJ

Conference Title

57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)

Pub Type

Conferences

Download Paper

https://doi.org/10.1109/FOCS.2016.19

Keywords

affine dispersers, Boolean circuits, lower bound

Citation

Find, M. , Golovnev, A. , Hirsch, E. and Kulikov, A. (2016), A better-than-3n lower bound for the circuit complexity of an explicit function, 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), New Brunswick, NJ, [online], https://doi.org/10.1109/FOCS.2016.19 (Accessed October 16, 2025)