Approximate Counting, Markov Chains and Phase Transitions
Organizers:
Markov chains play an important role in a variety of fields, but the analysis of their convergence properties remains a challenging problem. Our emphasis is on the analysis of "large" Markov chains, i.e., finite-state chains where the number of states is exponentially large as a function of the description size of an individual state. Such chains are especially important in the study of statistical physics models and the design of approximate counting algorithms. This workshop will bring together researchers in the analysis of large Markov chains from many areas of application, to review progress and to identify challenges for future research.
Recently there has been considerable success in designing approximate counting algorithms without the use of Markov chains, relying instead on so-called "spatial mixing" properties. Remarkably, matching hardness results have been established in the special case of antiferromagnetic 2-spin systems. This beautiful collection of results ties together the complexity of approximate counting on a general class of graphs with an associated phase transition for the infinite regular tree. By highlighting recent results in the study of approximate counting problems, the workshop will explore analogous connections for other models and for related problems.
All talks will be recorded. Enquiries may be sent to the organizers workshop_counting1 [at] lists.simons.berkeley.edu (at this address.)
Support is gratefully acknowledged from:
David Aldous (UC Berkeley), Alexander Barvinok (University of Michigan), Ivona Bezakova (Rochester Institute of Technology), Nayantara Bhatnagar (University of Delaware), Markus Bläser (Universität des Saarlandes), Michele Borassi (IMT Institute for Advanced Studies), Cornelius Brand (Saarland University), Guy Bresler (Massachusetts Institute of Technology), Raimundo Briceño (University of British Columbia), Andrei Bulatov (Simon Fraser Universeity), Jin-Yi Cai (University of Wisconsin-Madison), Pietro Caputo (Roma Tre University), Xi Chen (Columbia University), Radu Curticapean (Universität des Saarlandes), Artur Czumaj (University of Warwick), Holger Dell (Universität des Saarlandes), Amir Dembo (Stanford University), Persi Diaconis (Stanford University), Martin Dyer (University of Leeds), Charis Efthymiou (Georgia Tech), Funda Ergun (Indiana University), Fedor Fomin (University of Bergen), Peter Fulla (University of Oxford), Marylou Gabrié (École Normale Supérieure Paris), Andreas Galanis (University of Oxford), Shirshendu Ganguly (University of Washington), Leslie Ann Goldberg (University of Oxford), Catherine Greenhill (University of New South Wales), Heng Guo (Queen Mary, University of London), Mor Harchol-Balter (Carnegie Mellon University), Tom Hayes (University of New Mexico), Tyler Helmuth (UC Berkeley), Alexander Holroyd (Microsoft), Steve Homer (Boston University), Ravi Kannan (Microsoft Research India), Florent Krzakala (École Normale Supérieure Paris), John Lapinskas (University of Oxford), James Lee (University of Washington), Pinyan Lu (Shanghai University of Finance and Economics), Eyal Lubetzky (New York University), Brian Marcus (University of British Columbia), Fabio Martinelli (Roma Tre University), Andrea Montanari (Stanford University), Cris Moore (Santa Fe Institute), Elchanan Mossel (University of Pennsylvania and UC Berkeley), Emanuele Natale (Sapienza University of Rome), Mike Paterson (University of Warwick), Yuval Peres (Microsoft Research Redmond), Will Perkins (University of Birmingham), Dana Randall (Georgia Institute of Technology), David Richerby (University of Oxford), Marc Roth (Universität des Saarlandes), Justin Salez (Universite Paris Diderot), Vladas Sidoravicius (NYU-Shanghai and Courant Institute), Alistair Sinclair (UC Berkeley), Allan Sly (UC Berkeley), Alexandre Stauffer (University of Bath), Daniel Stefankovic (University of Rochester), Nike Sun (Massachusetts Institute of Technology), Prasad Tetali (Georgia Institute of Technology), Mario Ullrich (Johannes Kepler University Linz), Moshe Vardi (Rice University), Eric Vigoda (Georgia Institute of Technology), Mingji Xia (Institute of Software, Chinese Academy of Sciences), Jiaming Xu (University of Pennsylvania), Yitong Yin (Nanjing University), Lenka Zdeborova (Institut de Physique Théorique), Chihao Zhang (Shanghai Jiao Tong University), Stanislav Zivny (University of Oxford)
