Theoretical Computer Science research has produced and benefited from several powerful paradigms which bridge the discrete and continuous worlds—for instance, convex relaxations of combinatorial optimization problems, spectral graph theory, and Boolean Fourier analysis. In the past decade, several important advances—such as the construction of Ramanujan graphs of every degree, approximation algorithms for the asymmetric TSP, and results on the complexity of several counting problems related to statistical physics—have relied in one way or another on examining the zeros of certain multivariate polynomials derived from combinatorial objects. The power of this framework stems from the fact that certain classes of these polynomials occupy a sweet spot: they are general enough to encode a variety of interesting combinatorial, probabilistic and geometric data, and special enough to have useful global properties and structure theory.
This program will focus on emerging connections between the analytic theory of multivariate polynomials (sometimes called "the geometry of polynomials") and TCS as well as related fields such as combinatorics, probability, statistical physics, optimization and real algebraic geometry. The program is interdisciplinary and will gather researchers from the many communities with which this mathematical area makes contact.
The scientific content of the program will be organized into three broad areas, which are related but offer different entry points into the theory:
(1) Algorithms and Combinatorics
(2) Statistical Physics, Probability, and Counting
These are elaborated on in the workshop descriptions.
Organizers: Shayan Oveis Gharan (University of Washington; co-chair), Nikhil Srivastava (UC Berkeley; co-chair), Leonid Gurvits (City University of New York), Pablo Parrilo (Massachusetts Institute of Technology), Alistair Sinclair (UC Berkeley), David Wagner (University of Waterloo).
Long-Term Participants (tentative list, including organizers):
Miklós Abért (Rényi Institute), Nima Anari (Stanford University), Alexander Barvinok (University of Michigan), Peter Csikvari (Eötvös Loránd University), Shayan Oveis Gharan (University of Washington), Leonid Gurvits (City University of New York), Bill Helton (UC San Diego), Olga Holtz (UC Berkeley), Alexandra Kolla (University of Colorado, Boulder), Adam Marcus (Princeton University), Raghu Meka (UC Los Angeles), Pablo Parrilo (Massachusetts Institute of Technology), Will Perkins (Georgia Institute of Technology), Daniel Plaumann (Universität Konstanz), Doron Puder (Hebrew University of Jerusalem), Prasad Raghavendra (UC Berkeley), James Renegar (Cornell University), Mohan Ravichandran (Mimar Sinan University), Oded Regev (Courant Institute, New York University), Guus Regts (University of Amsterdam), Amin Saberi (Stanford University), Raman Sanyal (Goethe-Universität Frankfurt), Alistair Sinclair (UC Berkeley), Nikhil Srivastava (UC Berkeley), Piyush Srivastava (Tata Institute of Fundamental Research), Bernd Sturmfels (UC Berkeley), Nike Sun (UC Berkeley), Thorsten Theobald (Goethe-Universität Frankfurt), Levent Tunçel (University of Waterloo), Nisheeth Vishnoi (Ecole Polytechnique Fédérale de Lausanne), David Wagner (University of Waterloo).
Program image by Luisa Lee