All reports by Author Evgeny Demenkov:

__
TR11-026
| 27th February 2011
__

Evgeny Demenkov, Alexander Kulikov#### An Elementary Proof of $3n-o(n)$ Lower Bound on the Circuit Complexity of Affine Dispersers

Evgeny Demenkov, Alexander Kulikov

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