About
Several canonical results in the field of counting, such as the optimal approximation algorithm for the partition function of the hard-core model, are based on classical techniques such as decay of correlations and belief propagation. Recently, some of these results have been re-constructed or generalized by algebraic methods based on the geometry of zeros of univariate or multivariate polynomials associated with the problem. In some cases, these algebraic methods have beaten even the best known randomized algorithms based on Markov Chain Monte Carlo techniques; still, our understanding of the relative power of these methods is limited, and the best deterministic counting algorithm for the permanent of a nonnegative matrix has an approximation factor that is exponentially worse than the best randomized algorithm.
This workshop will bring together experts in deterministic counting to explore the state-of-the-art techniques developed in this field—for instance, the interpolation method, and the capacity method and its generalizations—as well as their limitations and connections to other topics such as the Lovász Local Lemma, mixed volumes, and operator scaling.
In addition to algorithms, we will also have several talks on extremal and structural questions in counting and probability (such as upper and lower bounds on the number of matchings in a regular graph, and central limit theorems for certain negatively associated distributions), which have been settled using methods related to polynomials.
Chairs/Organizers
Invited Participants
Dimitris Achlioptas (Central European University), Bibhas Adhikari (IIT Kharagpur), AmirMahdi Ahmadinejad (Stanford University), Nima Anari (Stanford University), Federico Ardila (San Francisco State University), Ferenc Bencs (Central European University), Ivona Bezáková (Rochester Institute of Technology), Petter Brändén (KTH Royal Institute of Technology), Johannes Buchmann (TU Darmstadt), Jin-Yi Cai (University of Wisconsin, Madison), Sarah Cannon (UC Berkeley), Charlie Carlson (University of Colorado Boulder), Yeshwanth Cherapanamjeri (UC Berkeley), Michael Chertkov (University of Arizona, Tucson), Péter Csikvári (Eötvös Loránd University), Ewan Davies (QuSoft, CWI and University of Amsterdam), Papri Dey (Max Planck Institute (MIS, Leipzig), Shirshendu Ganguly (UC Berkeley), Leslie Ann Goldberg (University of Oxford), F. Alberto Grunbaum (UC Berkeley), Heng Guo (University of Edinburgh), Tyler Helmuth (University of Bristol), Olga Holtz (UC Berkeley and Technische Universität Berlin), Fotis Iliopoulos (UC Berkeley), Katharina Victoria Jochemko (KTH Royal Institute of Technology), Ravi Kannan (Microsoft Research India), Alexandra Kolla (University of Colorado Boulder), Mario Kummer (TU Berlin), Zeph Landau (UC Berkeley), Rachel Lawrence (UC Berkeley), Jonathan Leake (UC Berkeley), Elliott Lieb (Princeton University), Kuikui Liu (University of Washington), Tianyu Liu (University of Wisconsin-Madison), Jingcheng Liu (UC Berkeley), Pinyan Lu (Shanghai University of Finance and Economics), Ryan Mann (University of Technology Sydney), Saeed Mehraban (Massachusetts Institute of Technology), Rafael Mendes de Oliveira (University of Toronto), Chuck Newman (NYU), Rad Niazadeh (Stanford University), 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), Rainer Sinn (Freie Universität Berlin), Nikhil Srivastava (UC Berkeley), Piyush Srivastava (Tata Institute of Fundamental Research), Bernd Sturmfels (UC Berkeley), Levent Tunçel (University of Waterloo), Nisheeth Vishnoi (Yale University), Jan Vondrák (Stanford University), David Wagner (University of Waterloo)
=========
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.