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, Barvinok’s homotopy method, and Gurvits’s 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.