Title: Generalizations of the Gate Elimination Method
Speaker: Alexander Golovnev, New York University
Date: Wednesday, February 17, 2016 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk we consider Boolean circuits over the full binary basis. It is known that almost all Boolean functions of nn variables require circuits of size Θ(2n/n)Θ(2n/n). At the same time, the best known lower bound of 3n−o(n)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 cncn 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 cc 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 involved substitutions, circuit complexity measures, and generalized circuit models that simplify and improve the analysis.
We show that affine dispersers are not computable by circuits of size 3.01n3.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:
http://eccc.hpi-web.de/report/2015/170/
http://eccc.hpi-web.de/report/2015/170/
See: http://www.cs.rutgers.edu/~allender/theory-spring16.html