Generalizations of the Gate Elimination Method

Wednesday, December 2, 2015 - 4:00pm to 5:00pm
Alexander Golovnev

Abstract:  In this talk we consider Boolean circuits over the full binary basis. It is known that almost all Boolean functions of $n$ variables require circuits of size $\Theta(2^n/n)$. At the same time, the best known lower bound $3n-o(n)$ for an explicit Boolean function (that is, a function from NP) was given by Blum in 1984. This bound, as well as most of the previous bounds, is based on a simple
method called gate elimination. The idea of the method is as follows: roughly, to prove a lower bound of $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 keeps the function in the same class; the bound then follows by induction.

In this talk, we discuss generalizations of gate elimination: we consider more evolved substitutions, circuit complexity measures, and generalized circuit models that simplify and improve the analysis. We show that affine disperser are not computable by circuits of size 3.01n. We also show that an explicit construction of dispersers for quadratic varieties (currently unknown) implies stronger lower bounds.

The talk is based on joint works with Magnus G. Find, Edward A. Hirsch, and Alexander S. Kulikov.