Workshops
Spring 2019

Deterministic Counting, Probability, and Zeros of Partition Functions

Mar. 18Mar. 22, 2019

Add to Calendar

Organizers:

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), Alexander Barvinok (University of Michigan), 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), Leonid Gurvits (City University of New York), Tyler Helmuth (University of Bristol), Zeph Landau (UC Berkeley), Jonathan Leake (UC Berkeley), Elliott Lieb (Princeton University), Tianyu Liu (University of Wisconsin-Madison), Pinyan Lu (Shanghai University of Finance and Economics), Ryan Mann (University of Technology Sydney), Saeed Mehraban (Massachusetts Institute of Technology), Chuck Newman (NYU), Will Perkins (University of Illinois at Chicago), Guus Regts (University of Amsterdam), David Ruelle (IHES), Alistair Sinclair (UC Berkeley), Alan Sokal (New York University), Piyush Srivastava (Tata Institute of Fundamental Research), Daniel Štefankovič (University of Rochester), Nisheeth Vishnoi (Yale University), Jan Vondrák (Stanford University), Yitong Yin (Nanjing University)

=========

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.