Algorithm Design Using Polynomials

In this talk I will present new methods for algorithm design and showcase results and breakthroughs obtained by looking through the lens of polynomials. I will start with the best known approximation algorithm for estimating the solution of the asymmetric traveling salesman problem, one of the oldest problems in computer science and optimization. Then, I will discuss a general framework based on computing inner products of polynomials that is used to design approximation algorithms for several important computational problems: volume maximization, counting matchings in bipartite graphs, Nash welfare maximization, and computing the permanent of positive semidefinite matrices.

Nima Anari is a postdoctoral researcher at Stanford University working with Amin Saberi. His research interests are in the design and analysis of algorithms, with a recent focus on applications of polynomials in this endeavor. He recently completed his Ph.D. in computer science at UC Berkeley, where he was advised by Satish Rao and was part of the theory group. Prior to that he received his B.Sc. in computer engineering and mathematics from Sharif university of technology.