Talk: On the Approximability of Polynomial Maximization over Convex Sets

Abstract: Approximation algorithms is a vast field of research and a substantial theory has been developed that has been very successful in determining optimal approximation algorithms for various classes of discrete optimization problems. 

My goal is to extend this beautiful theory to continuous optimization, where methods from discrete optimization encounter severe limitations. Such a theory is necessary, as natural and fundamental problems in various areas (such as compressed sensing or machine learning) are inherently continuous in nature. 

My work has focused on a rich class of continuous problems - polynomial maximization over convex sets. For various choices of polynomials and convex sets, this class captures a vast array of optimization problems spanning several disparate areas such as quantum information, machine learning, game theory, compressed sensing, constraint satisfaction, statistical physics, communication complexity, etc. 

Thus a unified theory of approximability for this class promises to be of broad scope and applicability. In this talk I discuss some progress we have made towards such a unified theory, highlighting that approximability depends crucially on the geometry of the set being optimized over. 

Bio: Vijay Bhattiprolu is a member at the School of Mathematics in the Institute for Advanced Study and a postdoctoral researcher at Princeton University. His research focuses on developing a unified theory of approximability for continuous optimization,  through the lens of the very rich class of problems that can be captured by polynomial maximization over convex sets. A Hallmark of his work is in using and further developing deep tools from analysis and convex geometry to study such questions in optimization. He obtained his Ph.D. from Carnegie Mellon University in July 2019 advised by Venkatesan Guruswami.