Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-026 | 27th February 2011 21:01

An Elementary Proof of $3n-o(n)$ Lower Bound on the Circuit Complexity of Affine Dispersers


Authors: Evgeny Demenkov, Alexander Kulikov
Publication: 27th February 2011 21:07
Downloads: 3996


A Boolean function $f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2$ is called an affine disperser for sources of dimension $d$, if $f$ is not constant on any affine subspace of $\mathbb{F}^n_2$ of dimension at least $d$. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for $d=o(n)$. The main motivation for studying such functions comes from extracting randomness from structured sources of imperfect randomness. In this paper, we show another application: we give a very simple proof of a $3n-o(n)$ lower bound on the circuit complexity (over the full binary basis) of affine dispersers. The same lower bound $3n-o(n)$ (but for a completely different function) was given by Blum in 1984 and is still the best known.

The main technique is to substitute variables by linear functions. This way the function is restricted to an affine subspace of $\mathbb{F}^n_2$. An affine disperser for $d=o(n)$ then guarantees that one can make $n-o(n)$ such substitutions before the function degenerates. It remains to show that each such substitution eliminates at least $3$ gates from a circuit.

ISSN 1433-8092 | Imprint