What's Happening in Fine Hall? Seminar: Polynomial Identity Testing

-
Zeev Dvir
Fine Hall Common Room

Given a multivariate polynomial over a field, how do you determine if it is the zero polynomial or not? There are many variants of this problem, most important of which is when the polynomial is given as a succinct formula  and "opening the parentheses"  is computationally infeasible as the number of monomials can be exponentially large. While there is a polynomial time *randomized* algorithm solving this problem, there is no deterministic solution in polynomial time (or even  slightly better than exponential). Closing this gap is one of the foremost challenges  in complexity theory and has deep connections to other important problems such as P vs NP. In this talk I will give an overview of the problem and some of the known results/connections.