Spring 2016

Counting Complexity and Phase Transitions

Jan. 11May 13, 2016

Research on exact and approximate counting problems has seen significant advances recently. The central aim is to understand the computational complexity of these problems and their relationship to phase transitions, especially in statistical physics. Counting problems may be conveniently expressed in terms of the evaluation of partition functions (a sum-of-product computation), and there are three related frameworks for studying them: constraint satisfaction problems, graph homomorphisms, and Holant problems. A satisfactory understanding of a counting problem involves establishing a classification theorem that delineates the regime in which the problem is solvable in polynomial time.

For exact counting, a number of strong dichotomy theorems have been achieved in all three frameworks, though many open problems remain. Furthermore, there is a general thesis that problems can be classified into one of the following three types according to the local constraint functions: (1) P-time computable, (2) #P-hard in general but P-time computable over planar structures, or (3) #P-hard even for planar structures. Moreover, type (2) corresponds to those problems that can be solved by holographic algorithms. The full extent of the validity of this thesis is open.

Classification of problem complexity for approximate counting is more challenging, and new complexity classes arise. For example, the problem #BIS of counting independent sets in a bipartite graph has emerged as a key problem of apparently intermediate complexity. Approximate counting also exhibits strong connections with statistical physics. On the positive side, Markov chain Monte Carlo and correlation decay provide two powerful techniques for achieving polynomial-time approximation algorithms. On the negative side, phase transitions appear to define the boundaries between easy and hard approximation problems.

Phase transitions also arise naturally in the study of random constraint satisfaction problems. Physically motivated algorithmic approaches such as survey propagation perform extremely well for these problems near the phase transition, but a rigorous understanding is only beginning to emerge.

This program brought together researchers from related fields to advance the state of art.


Jin-Yi Cai (University of Wisconsin-Madison; co-chair), Martin Dyer (University of Leeds; co-chair), Andrei Bulatov (Simon Fraser University), Xi Chen (Columbia University), Allan Sly (UC Berkeley)

Long-Term Participants (including Organizers):

David Aldous (UC Berkeley), Alexander Barvinok (University of Michigan), Ivona Bezáková (Rochester Institute of Technology), Nayantara Bhatnagar (University of Delaware), Markus Bläser (Universität des Saarlandes), Andrei Bulatov (Simon Fraser University), Peter Bürgisser (Technical University of Berlin), Jin-Yi Cai (University of Wisconsin-Madison; co-chair), Pietro Caputo (Università Roma Tre), Xi Chen (Columbia University), Colin Cooper (King's College London), Artur Czumaj (University of Warwick), Victor Dalmau (Universitat Pompeu Fabra), Varsha Dani (University of New Mexico), Persi Diaconis (Stanford University), Martin Dyer (University of Leeds; co-chair), Joanna Ellis-Monaghan (Saint Michael's College), Funda Ergun (Indiana University), Graham Farr (Monash University), Fedor Fomin (University of Bergen), Alan Frieze (Carnegie Mellon University), Leslie Ann Goldberg (University of Oxford), Catherine Greenhill (University of New South Wales), Mor Harchol-Balter (Carnegie Mellon University), Thomas Hayes (University of New Mexico), Pavol Hell (Simon Fraser University), Miki Hermann (École Polytechnique), Steve Homer (Boston University), Mark Jerrum (Queen Mary, University of London), Ravi Kannan (Microsoft Research India), Marek Karpinski (University of Bonn), Florent Krzakala (École Normale Supérieure Paris), Pinyan Lu (Shanghai University of Finance and Economics), Johann Makowsky (Technion Israel Institute of Technology), Fabio Martinelli (Università Roma Tre), Andrea Montanari (Stanford University), Cris Moore (Santa Fe Institute), Shayan Oveis Gharan (University of Washington), Michael Paterson (University of Warwick), Dana Randall (Georgia Institute of Technology), David Richerby (University of Oxford), Alistair Sinclair (Simons Institute, UC Berkeley), Allan Sly (UC Berkeley), Piyush Srivastava (California Institute of Technology), Daniel Štefankovič (University of Rochester), Prasad Tetali (Georgia Institute of Technology), Eric Vigoda (Georgia Institute of Technology), Mingji Xia (Chinese Academy of Sciences), Yitong Yin (Nanjing University), Lenka Zdeborová (CEA Saclay), Stanislav Zivny (University of Oxford)

Research Fellows:

Radu Curticapean (Saarland University), Holger Dell (Saarland University and Cluster of Excellence, MMCI), Andreas Galanis (University of Oxford), Heng Guo (Queen Mary, University of London; Google Research Fellow), Nike Sun (UC Berkeley; Microsoft Research Fellow), Jiaming Xu (University of Pennsylvania)

Visiting Graduate Students and Postdocs:

Antonio Blanca (UC Berkeley), Michele Borassi (IMT Institute for Advanced Studies), Cornelius Brand (Saarland University), Raimundo Briceño (University of British Columbia), Laura Florescu (New York University), Peter Fulla (University of Oxford), Marylou Gabrié (École Normale Supérieure Paris), Shirshendu Ganguly (University of Washington), Tyler Helmuth (UC Berkeley), Fotis Iliopoulos (UC Berkeley), John Lapinskas (University of Oxford), Jingcheng Liu (UC Berkeley), Emanuele Natale (Max Planck Institute, Saarbrücken), Marc Roth (Saarland University), Manuel Sabin (UC Berkeley), Tselil Schramm (UC Berkeley), Chihao Zhang (Shanghai Jiao Tong University), Yumeng Zhang (UC Berkeley)


Monday, Jan. 25Thursday, Jan. 28, 2016


Jin-Yi Cai (University of Wisconsin-Madison; co-chair), Martin Dyer (University of Leeds; co-chair), Andrei Bulatov (Simon Fraser University), Xi Chen (Columbia University), Allan Sly (UC Berkeley)
Monday, Feb. 22Friday, Feb. 26, 2016


Eric Vigoda (Georgia Institute of Technology; chair), Martin Dyer (University of Leeds), Catherine Greenhill (University of New South Wales), Allan Sly (UC Berkeley)
Monday, Mar. 28Friday, Apr. 1, 2016


Jin-Yi Cai (University of Wisconsin-Madison; chair), Alexander Barvinok (University of Michigan), Xi Chen (Columbia University), Mark Jerrum (Queen Mary, University of London)
Monday, May 2Friday, May 6, 2016


Andrei Bulatov (Simon Fraser University; chair), Amin Coja-Oghlan (Goethe University Frankfurt am Main), Alan Frieze (Carnegie Mellon University), Mike Molloy (University of Toronto), Andrea Montanari (Stanford University)
Monday, Jun. 5Thursday, Jun. 8, 2017


Jin-Yi Cai (University of Wisconsin-Madison; co-chair), Martin Dyer (University of Leeds; co-chair), Andrei Bulatov (Simon Fraser University), Xi Chen (Columbia University), Allan Sly (UC Berkeley)

Program image: "Phase Transition" by Maryam Hayati.

Past Internal Program Activities

Friday, April 29th, 2:30 pm3:30 pm
Heng Guo (Queen Mary, University of London)
Friday, April 22nd, 2:00 pm3:00 pm
Fedor Fomin (University of Bergen)
Friday, April 15th, 2:00 pm3:00 pm
Jiaming Xu (University of Pennsylvania)
Friday, April 8th, 2:00 pm3:00 pm
Johann A. Makowsky (Technion Israel Institute of Technology)
Friday, April 1st, 2:00 pm3:00 pm
Friday, March 18th, 2:00 pm3:00 pm
Yumeng Zhang (UC Berkeley)
Friday, March 11th, 2:00 pm3:00 pm
Alan Frieze (Carnegie Mellon University)
Friday, March 4th, 2:00 pm3:00 pm
Catherine Greenhill (University of New South Wales)
Friday, February 19th, 2:00 pm3:00 pm
Ali Eshragh (University of Newcastle, Australia)
Friday, February 12th, 2:00 pm3:00 pm
John Lapinskas (University of Oxford)
Friday, February 5th, 2:00 pm3:00 pm
Martin Dyer (University of Leeds)