From the Inside: Counting Complexity and Phase Transitions

by Allan Sly

Counting is of course one of the oldest branches of mathematics. Faced with a set of constraints, the first question we might ask is whether they can all be satisfied. And then the natural follow-up question is how many ways there are to do it. For example, suppose we have a social network: one could ask how many ways there are to split the group into pairs such that each pair are friends. In combinatorics, this means counting perfect matchings on a graph. The number of ways to split a network into 3 groups so that no two persons in any group are acquainted is the problem of counting graph 3-colourings. Many other natural combinatorial problems also translate into counting problems.

One of the primary goals of the Spring 2016 Simons Institute program on Counting Complexity and Phase Transitions is to classify the computational complexity of different counting problems, a topic that has already seen remarkable success. Some constraints, such as the XOR of variables, amount to solving linear equations, and so solutions can be counted efficiently using linear algebra. The problems of counting solutions to constraint satisfaction problems (CSPs) split into two classes, those which are polynomial-time computable and those which are #P-complete (and therefore as hard as any CSP). The latter group can itself be split into problems that are #Pcomplete even on planar graphs and those that can be computed in polynomial time on planar graphs, such as counting perfect matchings. One exciting development of the program is that all examples of Boolean CSPs that are tractable on planar graphs but not tractable in general can be solved by a holographic algorithm, a beautiful technique of equating seemingly different counting problems. After a simple "do nothing" transformation, these problems can be solved using Kastelyn's algorithm for counting perfect matchings in a planar graph.

Another focus of the program is the regime where constraints are selected at random. Such questions have long been studied in combinatorics; a well-known example is finding the number of colors needed to color a random graph. But a more comprehensive and unified understanding of random CSPs has only been achieved with the application of ideas originating in statistical mechanics to study phase transitions of spin glasses. In physics, spin glasses are magnetics systems such as certain alloys of metals where magnetic particles have both positive and negative interactions arranged in a random order. This disordered collection of interactions was found to share similar behavior to random CSPs.

Phase transitions in matter occur when one state of matter changes to another, as in water freezing into ice or evaporating into steam as the temperature changes. A similar series of transitions has been proposed by physicists for random CSPs as the number of constraints is increased; analysis yields a detailed picture of the geometric arrangement of solutions arrayed in clusters. This theory has led to precise predictions of when the constraint satisfaction problem is satisfiable, and a count of the number of solutions. Through the lens of mathematics, these deep predictions appear at first glance to rest on dazzling leaps of faith, though recently many aspects of this picture have been established as rigorous mathematics. The Simons Institute program has brought physicists together with computer scientists and mathematicians to share techniques, ideas and intuitions from their respective fields. The program kicked off with a boot camp, which brought together the participants from all of the fields represented in the program and introduced the many different approaches to counting including ideas from physics as well as algebraic, probabilistic and combinatorial methods.

In February, our second workshop focused on approximate counting and Markov Chain Monte Carlo, a class of algorithms used to sample from complicated and high dimensional distributions. These two topics are closely linked, as in many cases approximate counting and approximate sampling from what is being counted go hand in hand. A recurring theme throughout the workshop was the role correlation decay plays in both counting algorithms and other Markov chains, where correlations over long distances are often closely linked to computational hardness of approximate counting.

The third workshop focused on classifying the computational complexity of different classes of counting problems. A remarkably comprehensive picture is known for many of these classes. Still we heard that interesting questions remain, such as the complexity of approximately counting graph homomorphisms into certain graphs on just four vertices.

The final workshop (May 2 - 6) will focus on random instances of counting problems, particularly progress made establishing the heuristics from physics. In particular, the study of random bipartite graphs plays a central role in approximate counting problems on sparse graphs. One conclusion that has become clear from the program is that the situation for sparse hypergraphs is more complicated and calls for a new set of ideas.

Related Articles:

Letter from the Director, Spring 2016
From the Inside: Algorithmic Challenges in Genomics
Research Vignette: Strengthening SETH Lower Bounds
Research Vignette: Simplicity, Optimality and Efficiency Tradeoffs in Economics
Looking Ahead: Logic and Uncertainty