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.
sympa [at] lists [dot] simons [dot] berkeley [dot] edu (body: subscribe%20geometry2019announcements%40lists.simons.berkeley.edu) (Click here to subscribe to our announcements email list for this program).
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), Ivona Bezáková (Rochester Institute of Technology), Petter Brändén (KTH Royal Institute of Technology in Stockholm), Johannes Buchmann (TU Darmstadt), Péter Csikvári (Eötvös Loránd University), Shirshendu Ganguly (UC Berkeley), F. Alberto Grunbaum (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), Ravi Kannan (Microsoft Research India), Alexandra Kolla (University of Colorado Boulder), Mario Kummer (TU Berlin), Chuck 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 (Florida Atlantic University), David Ruelle (IHES), Amin Saberi (Stanford University), Raman Sanyal (Goethe University Frankfurt), Peter Sarnak (IAS), Claus Scheiderer (Universität Konstanz), Boris Shapiro (KTH Royal Institute of Technology), Alistair Sinclair (UC Berkeley), Nikhil Srivastava (UC Berkeley), Daniel Štefankovič (University of Rochester), Bernd Sturmfels (UC Berkeley), Thorsten Theobald (Goethe Universität Frankfurt am Main), Levent Tunçel (University of Waterloo), Nisheeth Vishnoi (Yale University), Jan Vondrák (Stanford University)
Nima Anari (Stanford University), Ewan Davies (QuSoft, CWI and University of Amsterdam), Papri Dey (Max Planck Institute), 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), Marie-Charlotte Brandenburg (Freie Universität Berlin), Sarah Cannon (UC Berkeley), Charlie Carlson (University of Colorado Boulder), Yeshwanth Cherapanamjeri (UC Berkeley), Anthony Della Pella (University of Michigan), Fotis Iliopoulos (UC Berkeley), Jingcheng Liu (UC Berkeley), Kuikui Liu (University of Washington), Rad Niazadeh (Stanford University)
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