A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function

Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov

Research outputpeer-review

8 Citations (Scopus)

Abstract

We consider Boolean circuits over the full binary basis. We prove a (3+1/86)n-o(n) lower bound onthe size of such a circuit for an explicitly definedpredicate, namely an affine disperser for sublinear dimension. 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.

Original languageEnglish
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE Computer Society
Pages89-98
Number of pages10
ISBN (Electronic)9781509039333
DOIs
Publication statusPublished - 14 Dec 2016
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick
Duration: 9 Oct 201611 Oct 2016

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2016-December
ISSN (Print)0272-5428

Conference

Conference57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
CountryUnited States
CityNew Brunswick
Period9/10/1611/10/16

    Fingerprint

Scopus subject areas

  • Computer Science(all)

Cite this

Find, M. G., Golovnev, A., Hirsch, E. A., & Kulikov, A. S. (2016). A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. In Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 (pp. 89-98). [7782921] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2016-December). IEEE Computer Society. https://doi.org/10.1109/FOCS.2016.19