ÍâÍøÌìÌÃ

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.