Spring 2019

Geometry of Polynomials

Jan. 15May 17, 2019

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
(3) Optimization

These are elaborated on in the workshop descriptions.

This program is supported in part by the National Science Foundation and by the Patrick J. McGovern Foundation.



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 (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), Péter Csikvári (Eötvös Loránd University), Shirshendu Ganguly (UC Berkeley), F. Alberto Grünbaum (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; co-chair), 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 (Florida Atlantic University), David Ruelle (IHES), Amin Saberi (Stanford University), Raman Sanyal (Goethe University Frankfurt), Peter Sarnak (Princeton University), Claus Scheiderer (Universität Konstanz), Boris Shapiro (KTH Royal Institute of Technology), Alistair Sinclair (UC Berkeley), Nikhil Srivastava (UC Berkeley; co-chair), 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), Yitong Yin (Nanjing University)

Research Fellows:

Nima Anari (Stanford University; Microsoft Research Fellow), Ewan Davies (QuSoft, CWI and University of Amsterdam; Research Fellow), Papri Dey (Max Planck Institute (MIS, Leipzig); Research Fellow), Katharina Victoria Jochemko (KTH Royal Institute of Technology; Microsoft Research Fellow), 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), Charles Carlson (University of Colorado Boulder), Yeshwanth Cherapanamjeri (UC Berkeley), Anthony Della Pella (University of Michigan), Fotis Iliopoulos (UC Berkeley), Archit Kulkarni (UC Berkeley), Rachel Lawrence (UC Berkeley), Jonathan Leake (UC Berkeley), Jingcheng Liu (UC Berkeley), Kuikui Liu (University of Washington), Theo McKenzie (UC Berkeley), Sidhanth Mohanty (UC Berkeley), Rad Niazadeh (Stanford University), Aaron Schild (UC Berkeley), Anna Seigal (UC Berkeley), Jorge Garza Vargas (UC Berkeley), Elizabeth Yang (UC Berkeley), Kostas Zempetakis (UC Santa Cruz)


Tuesday, Jan. 22Friday, Jan. 25, 2019


Shayan Oveis Gharan (University of Washington), Nikhil Srivastava (UC Berkeley)
Monday, Feb. 11Friday, Feb. 15, 2019


Shayan Oveis Gharan (University of Washington; chair), Nikhil Srivastava (UC Berkeley)
Monday, Mar. 18Friday, Mar. 22, 2019


Alistair Sinclair (UC Berkeley; chair), Alexander Barvinok (University of Michigan), Leonid Gurvits (City University of New York)
Tuesday, Apr. 30Friday, May 3, 2019


Bernd Sturmfels (UC Berkeley; chair), Michel Goemans (Massachusetts Institute of Technology), Pablo Parrilo (Massachusetts Institute of Technology), Jim Renegar (Cornell University)
Tuesday, Sep. 8Friday, Sep. 11, 2020


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)

The workshops in the "Geometry of Polynomials" program are supported in part by the National Science Foundation under Award No. 1835986.

We are required by the NSF Proposal & Award Policies & Procedures Guide (Chapter II.E.7), effective January 28, 2019, to provide all event participants with information on the University’s policy on sexual and other forms of harassment or sexual assault as well as directions on how to report any violations of this policy. For purposes of this requirement, “other forms of harassment” is defined as “non-gender or non-sex-based harassment of individuals protected under federal civil rights laws, as set forth in organizational policies or codes of conduct, statutes, regulations, or executive orders.” This information is available here.

Program image by Luisa Lee

Past Internal Program Activities

Wednesday, May 8th, 10:30 am12:00 pm
Liam Solus (KTH Stockholm)
Wednesday, April 24th, 11:30 am12:30 pm
Daniel Plaumann (TU Dortmund)
Wednesday, April 17th, 11:30 am12:30 pm
Ewan Davies, Simons Institute
Wednesday, April 17th, 10:15 am11:15 am
Shirshendu Ganguly, UC Berkeley
Thursday, April 4th, 10:00 am12:00 pm
Raman Sanyal
Wednesday, March 27th, 10:30 am12:00 pm
Charles Anthony Carlson (University of Colorado, Boulder)
Monday, March 25th, 9:00 am5:00 pm
Wednesday, March 6th, 10:30 am12:00 pm
Sarah Cannon (UC Berkeley)
Wednesday, February 20th, 10:30 am12:00 pm
Mario Kummer, TU Berlin
Thursday, February 7th, 2:00 pm3:30 pm
Kuikui Liu
Thursday, February 7th, 11:00 am12:00 pm
Yuri Tschinkel (Simons Foundation / NYU)
Thursday, February 7th, 9:30 am11:00 am
Kuikui Liu
Wednesday, February 6th, 10:30 am12:00 pm
Bernd Sturmfels, MPI Leipzig and UC Berkeley
Monday, February 4th, 9:00 am5:00 pm
Wednesday, January 30th, 10:30 am12:00 pm
Peter Csikvari