ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

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

RSS-Feed




Revision #1
Authors: Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov
Accepted on: 16th February 2016 19:38
Downloads: 188
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: 1030
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