All reports by Author Magnus Gausdal Find:

__
TR15-166
| 17th October 2015
__

Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov#### A better-than-$3n$ lower bound for the circuit complexity of an explicit function

Revisions: 2

Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov

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