Events Spring 2019

Open Lecture — The Polynomial Paradigm in Algorithms

Mar 11, 2019 4:00 pm – 5:00 pm 

Add to Calendar


Shayan Oveis Gharan (University of Washington) and Nikhil Srivastava (UC Berkeley)

We will discuss the fruitful paradigm of encoding discrete phenomena in complex multivariate polynomials, and understanding them via the interplay of the coefficients, zeros, and function values of these polynomials. For example, the states of a statistical physics model and the corresponding phase transition, the clusters in a graph, and the convex cones of linear and semidefinite programming can all be viewed in these terms. Over the last fifteen years, this perspective has led to several breakthroughs in computer science, and an unexpected bridge between distant scientific areas including combinatorics, probability, statistical physics, convex and algebraic geometry, and computer science has been built. In this talk we will introduce and discuss several classes of these polynomials and their surprising applications.

Light refreshments will be served before the lecture at 3:30 p.m.