Spring 2019

Deterministic Counting, Probability, and Zeros of Partition Functions

Mar. 18Mar. 22, 2019

Add to Calendar


Alistair Sinclair (UC Berkeley; chair), Alexander Barvinok (University of Michigan), Leonid Gurvits (City University of New York)

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.

Further details about this workshop will be posted in due course. Enquiries may be sent to the organizers workshop-geometry2 [at] lists [dot] simons [dot] berkeley [dot] edu (at this address).

All events take place in the Calvin Lab auditorium.

Registration is required to attend this workshop. To submit your name for consideration, please register and await confirmation of your acceptance to the workshop before booking your travel. Space may be limited, and you are advised to register early.

Invited Participants: 

Nima Anari (Stanford University), Ferenc Bencs (Central European University), Petter Brändén (KTH Royal Institute of Technology in Stockholm), Péter Csikvári (Eötvös Loránd University), Leslie Ann Goldberg (University of Oxford), Heng Guo (University of Edinburgh), Tyler Helmuth (University of Bristol), Jonathan Leake (UC Berkeley), Elliott Lieb (Princeton University), Pinyan Lu (Shanghai University of Finance and Economics), Saeed Mehraban (Massachusetts Institute of Technology), Chuck Newman (NYU), Will Perkins (University of Illinois at Chicago), Guus Regts (University of Amsterdam), David Ruelle (IHES), Piyush Srivastava (Tata Institute of Fundamental Research), Nisheeth Vishnoi (Yale University), Jan Vondrák (Stanford University), Yitong Yin (Nanjing University)