ECCC-Report TR15-166https://eccc.weizmann.ac.il/report/2015/166Comments and Revisions published for TR15-166en-usTue, 16 Feb 2016 19:38:30 +0200
Revision 1
| A better-than-$3n$ lower bound for the circuit complexity of an explicit function |
Magnus Gausdal Find,
Alexander Golovnev,
Edward Hirsch,
Alexander Kulikov
https://eccc.weizmann.ac.il/report/2015/166#revision1We 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.Tue, 16 Feb 2016 19:38:30 +0200https://eccc.weizmann.ac.il/report/2015/166#revision1
Paper TR15-166
| A better-than-$3n$ lower bound for the circuit complexity of an explicit function |
Alexander Kulikov,
Magnus Gausdal Find,
Edward Hirsch,
Alexander Golovnev
https://eccc.weizmann.ac.il/report/2015/166We 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.Sat, 17 Oct 2015 19:13:36 +0300https://eccc.weizmann.ac.il/report/2015/166