What's Happening in Fine Hall? Seminar: Polynomial Identity Testing
What's Happening in Fine Hall? Seminar: Polynomial Identity Testing
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.