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).

Registration is required to attend this workshop. Space may be limited, and you are advised to register early. The link to the registration form will appear on this page approximately 10 weeks before the workshop. To submit your name for consideration, please register and await confirmation of your acceptance before booking your travel.

Invited Participants: 

Nima Anari (Stanford University), Ferenc Bencs (Central European University), Ivona Bezáková (Rochester Institute of Technology), Marek Biskup (UCLA), Petter Brändén (KTH Royal Institute of Technology in Stockholm), Jin-Yi Cai (University of Wisconsin, Madison), 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), Zeph Landau (UC Berkeley), Jonathan Leake (UC Berkeley), Elliott Lieb (Princeton University), Pinyan Lu (Shanghai University of Finance and Economics), Ryan Mann (University of Technology Sydney), Saeed Mehraban (Massachusetts Institute of Technology), Charles Newman (NYU), William Perkins (University of Illinois at Chicago), Guus Regts (University of Amsterdam), David Ruelle (IHES), Alan Sokal (University College London), Piyush Srivastava (Tata Institute of Fundamental Research), Daniel Štefankovič (University of Rochester), Nisheeth Vishnoi (École polytechnique fédérale de Lausanne), Jan Vondrák (Stanford University), Yitong Yin (Nanjing University)