Title: Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
Speaker: Rafael Oliveira, Princeton University
Date: Wednesday, February 4, 2015 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Derandomization of the Polynomial Identity Testing problem is one of the most basic and challenging problems in Algebraic Complexity. Despite much effort, derandomizing PIT seems to be a hard task even for restricted models of computation, including small depth circuits computing multilinear polynomials. In this talk, we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we also obtain lower bounds for these models.
We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known.
Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs).
Joint work with Amir Shpilka and Ben Lee Volk, from Tel Aviv University.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S15/