NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
A better-than-3n lower bound for the circuit complexity of an explicit function
Published
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)
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)