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.
This program is supported in part by the National Science Foundation and by the Patrick J. McGovern Foundation.
Long-Term Participants (including Organizers):
Visiting Graduate Students and Postdocs:
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