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).
Long-Term Participants (tentative list, including organizers):
Bibhas Adhikari (IIT Kharagpur), Federico Ardila (San Francisco State University), Alexander Barvinok (University of Michigan), Petter Brändén (KTH Royal Institute of Technology in Stockholm), Johannes Buchmann (TU Darmstadt), 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 Illinois at Urbana-Champaign), Mario Kummer (TU Berlin), Charles Newman (NYU), Shayan Oveis Gharan (University of Washington), 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), Nisheeth Vishnoi (Ecole Polytechnique Fédérale de Lausanne), Jan Vondrák (Stanford University)
Nima Anari (Stanford University), Ewan Davies (QuSoft, CWI and University of Amsterdam), Papri Dey (Max Planck Institute (MIS, Leipzig)), Katharina Victoria Jochemko (KTH Royal Institute of Technology), Rafael Mendes de Oliveira (University of Toronto), Rainer Sinn (Freie Universität Berlin), Piyush Srivastava (Tata Institute of Fundamental Research)
Visiting Graduate Students and Postdocs:
Amirmahdi Ahmadinejad (Stanford University), Charlie Carlson (University of Colorado Boulder), Anthony Della Pella (University of Michigan), Yusuf Hakan Kalayci (Bogazici University), Kuikui Liu (University of Washington), Rad Niazadeh (Stanford University), Alireza Rezaei (University of Washington), Anna Seigal (UC Berkeley).
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