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):
Miklos Abert (Alfréd Rényi Institute of Mathematics), Bibhas Adhikari (IIT Kharagpur), Alexander Barvinok (University of Michigan), Petter Brändén (KTH Royal Institute of Technology in Stockholm), Peter Csikvari (Eötvös Loránd University), Shirshendu Ganguly (UC Berkeley), Heng Guo (University of Edinburgh), Leonid Gurvits (City University of New York), Bill Helton (UC San Diego), Olga Holtz (UC Berkeley and Technische Universität Berlin), Alexandra Kolla (University of Colorado Boulder), Mario Kummer (TU Berlin), Shayan Oveis Gharan (University of Washington), Pablo Parrilo (Massachusetts Institute of Technology), Will Perkins (University of Illinois at Chicago), Daniel Plaumann (Technical University of Dortmund), Prasad Raghavendra (UC Berkeley), Mohan Ravichandran (Mimar Sinan University), Guus Regts (University of Amsterdam), Jim Renegar (Cornell University), Zvi Rosen (UC Berkeley), David Ruelle (IHES), Amin Saberi (Stanford University), Raman Sanyal (Goethe University Frankfurt), Claus Scheiderer (Universität Konstanz), Alistair Sinclair (UC Berkeley), Nikhil Srivastava (UC Berkeley), Bernd Sturmfels (UC Berkeley), Thorsten Theobald (Goethe Universität Frankfurt am Main), Levent Tunçel (University of Waterloo), Jan Vondrák (Stanford University), David Wagner (University of Waterloo).
Rainer Sinn (Freie Universität Berlin), Katharina Victoria Jochemko (KTH Royal Institute of Technology), Papri Dey (Max Planck Institute), Ewan Davies (QuSoft, CWI and University of Amsterdam), Piyush Srivastava (Tata Institute of Fundamental Research), Nima Anari Ahmadipouranari (Stanford University), Rafael Mendes de Oliveira (University of Toronto).
Those interested in participating in this program should send email to the organizers geometry2019 [at] lists [dot] simons [dot] berkeley [dot] edu (at this address).
Program image by Luisa Lee