Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR15-166 | 19th August 2022 22:39

Improving $3n$ Circuit Complexity Lower Bounds

RSS-Feed




Revision #2
Authors: Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov
Accepted on: 19th August 2022 22:39
Downloads: 5
Keywords: 


Abstract:

Proving circuit lower bounds remains a tremendously difficult problem. Although it can be easily shown by counting that almost all Boolean predicates of $n$ variables have circuit size $\Omega(2^n/n)$, we have no example of an $\mathbf{NP}$ function requiring even a superlinear number of gates. Moreover, only modest linear lower bounds are known. Until recently, the strongest known lower bound was $3n-o(n)$ presented by Blum in 1984. In 2011, Demenkov and Kulikov presented a much simpler proof of the same lower bound, but for a more complicated function --- an affine disperser for sublinear dimension. Informally, this is a function that is resistant to any $n-o(n)$ affine substitutions. In 2011, Ben-Sasson and Kopparty gave an explicit construction of such a function. The proof of the lower bound basically goes by showing that for any circuit there exists an affine hyperplane where the function complexity decreases at least by three gates. In this paper, we prove the following two extensions.

1. We prove a $\left(3+\frac{1}{86}\right)n-o(n)$ lower bound for the circuit size of an affine disperser for sublinear dimension. 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.

2. We then present a much simpler proof of a stronger lower bound of $3.11n$ for a quadratic disperser. Informally, a quadratic disperser is resistant to sufficiently many substitutions of the form $x \gets p$, where $p$ is a polynomial of degree at most two. Currently, there are no constructions of quadratic dispersers in $\mathbf{NP}$ (although there are constructions over large fields, and constructions with weaker parameters over $\mathrm{GF}(2)$). The key ingredient of this proof is the induction on the size of the underlying quadratic variety instead of the number of variables as in the previously known proofs.



Changes to previous version:

In this revision, we fix an error in the case analysis, significantly change the presentation of the case analysis, and we include a lower bound for quadratic dispersers from https://eccc.weizmann.ac.il/report/2015/170/


Revision #1 to TR15-166 | 16th February 2016 19:38

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





Revision #1
Authors: Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov
Accepted on: 16th February 2016 19:38
Downloads: 2658
Keywords: 


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 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.



Changes to previous version:

We fixed some inaccuracies and simplified the presentation.


Paper:

TR15-166 | 17th October 2015 18:18

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





TR15-166
Authors: Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov
Publication: 17th October 2015 19:13
Downloads: 2823
Keywords: 


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 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.



ISSN 1433-8092 | Imprint