Abstract
It is known that a random Boolean function on $n$ variables requires circuits of size $\Theta(2^n/n)$. At the same time, the strongest known lower bound $3n-o(n)$ for an explicit Boolean function (that is, a function from NP) was given by Blum more than 30 years ago. This bound, as well as most of the previous bounds, is based on a simple method called gate elimination. Its idea is straightforward: roughly, to prove a lower bound $cn$ for a function from a certain class one shows that in any circuit computing a function from the class one can find a substitution of a constant to an input variable that eliminates at least c gates from a circuit and leaves a subfunction from the same class; the bound then follows by induction.
In this talk, we will discuss ways of generalizing the gate elimination method for proving circuit lower bounds. First, we will present a slightly stronger than $3n$ lower bound for affine dispersers. These are functions that are not constant on any affine subspace of sufficiently large dimension. Equivalently, such functions do not degenerate under sufficiently many linear substitutions. We will then show that an explicit construction of dispersers for quadratic varieties (currently unknown) implies stronger lower bounds. Informally, these are functions that survive even under quadratic (but not only linear) substitutions.