Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AFFINE DISPERSER:
Reports tagged with affine disperser:
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: 1

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

ISSN 1433-8092 | Imprint