Random Constraint Satisfaction

Monday, July 17

09:00 - 09:30 Self-Registration
09:30 - 11:00 Amin Coja-Oghlan: An introduction to random constraint satisfaction problems
11:00 - 11:30 Coffee break
11:30 - 12:30 Mihyun Kang: Core forging and local limit theorems for the k-core of random graphs
12:30 - 14:00 Lunch break
14:00 - 15:30 Christopher Moore: Classic Bounds on the k-SAT Threshold
15:30 - 16:00 Coffee break
16:00 - 17:00 Problem session

Tuesday, July 18

09:00 - 10:30 Daniel Stefankovic: Spin models on trees and random regular graphs
10:30 - 11:00 Group Photo & Coffee break
11:00 - 12:30 Amin Coja-Oghlan: Boltzmann distributions
12:30 - 14:00 Lunch break
14:00 - 15:30 Christopher Moore: Community detection and the stochastic block model: belief propagation and the Kesten-Stigum threshold
15:30 - 16:00 Coffee break
16:00 - 17:00 Problem session

Wednesday, July 19

09:00 - 10:30 Daniel Stefankovic: Spin models on trees and random regular graphs
10:30 - 11:00 Coffee break
11:00 - 12:30 Amin Coja-Oghlan: Factor graphs and Belief Propagation
12:30 - 14:00 Lunch break
14:00 - 16:30 Excursion: tba

Friday, July 21

09:00 - 10:30 Christopher Moore: The conjectured hard regime and open questions
10:30 - 11:00 Coffee break
11:00 - 12:30 Daniel Stefankovic: Spin models on trees and random regular graphs
12:30 - 14:00 Lunch break, end of school

Christopher Moore: Classic Bounds on the k-SAT Threshold

Before condensation, contiguity, and sophisticated random variables based on clustering, there were first and second moment bounds on the k-SAT threshold, showing that it grows as O(2^k), and differential equations that show how to find satisfying assignments up to O(2^k/k); Relax and enjoy these golden oldies from the 1990s and early 2000s, and brush up on your discrete probability and asymptotic combinatorics.

Christopher Moore: Community detection and the stochastic block model: belief propagation and the Kesten-Stigum threshold

The stochastic block model is a model of random graphs with planted community structure, popular in the study of social and biological networks.  I’ll define it and describe a Belief Propagation algorithm for it (which is an especially easy setting in which to learn about Belief Propagation).  I’ll then describe the Kesten-Stigum threshold, above which community detection becomes easy, in terms of the linear stability of a trivial fixed point into which BP can fall.  This will include an analysis of the non-backtracking matrix, which can also be used for spectral clustering (Krzakala et al., PNAS, and Bordenave-Lelarge-Massoulie).

Christopher Moore: Information-theoretic thresholds on the block model: the second moment method and contiguity

Well below the Kesten-Stigum threshold is an information-theoretic barrier, below which community detection is impossible regardless of our computational resources.  Not only can we not label vertices better than chance — we can’t even tell whether communities exist, i.e., distinguish the block model from a null model without community structure (the Erdos-Renyi graph).  I’ll explain the idea of contiguity and show how second moment bounds provide a sufficient condition for indistinguishability.  (This is joint work with Jess Banks, Joe Neeman, and Praneeth Netrapalli.)

Christopher Moore: The conjectured hard regime and open questions

Between the information-theoretic threshold and the Kesten-Stigum threshold is a zone where community detection is information-theoretically possible, but where we believe it requires an exponential amount of computation. For instance, we believe that Monte Carlo Markov Chain algorithms with a uniform initial state will take exponential time to find a state correlated with the planted one, and that Belief Propagation will evolve to the trivial fixed point from all but an exponentially small fraction of initial messages. I’ll give the physical intuition behind these claims (from Decelle et al.) and wave my hands about how they might be proved.

Mihyun Kang: Core forging and local limit theorems for the k-core of random graphs

The k-core of a graph is the largest subgraph of minimum degree k. The k-core can be determined algorithmically by the peeling process that removes an arbitrary vertex of degree less than k while there is one. In one of the most influential contributions to the theory of random graphs, Pittel, Spencer and Wormald analysed the peeling process on the Erdös-Rényi random graph and determined the precise threshold d_k from where the k-core is non-empty whp. Since this seminar work the k-core problem has extensively been studied, not least due to its connections with other questions in combinatorics and computer science. For example, cores play a very important role in the study of random constraint satisfaction problems such as random k-SAT or random graph colouring. While most of the previous work on the k-core problem has been based on the peeling process, in this talk we shall present a very different approach and devise a generative model of graphs with a k-core of a given order and size. It is inspired by the Warning Propagation message passing algorithm, which allows us to describe succinctly how the k-core is embedded into the rest of the graph, the mantle. We also establish a multivariate local limit theorem for the joint distribution of the order and size of the k-core of the Erdös-Rényi random graph as well as several other parameters that are of combinatorial significance to understand the way the core is embedded into the mantle. (Joint work with Amin Coja-Oghlan, Oliver Cooley, and Kathrin Skubch)

Will Perkins: Planted satisfiability and refutation: algorithms and barriers

Consider the following two algorithmic tasks: 1) find the "planted" solution to a random k-SAT formula generated in such a way that a particular assignment is guaranteed to be satisfying 2) at densities above the satisfiability threshold, efficiently certify that a random k-SAT formula has no satisfying assignments.

For certain planted distributions and certain predicates, both planted satisfiability and the CSP refutation problem are conjectured to be computationally intractable at low enough clause densities.  If so, this would provide a means of generating hard instances of an NP-hard problem, and have implications in cryptography and hardness of approximation.  But what rigorous evidence do we have of such intractability?  I will survey known algorithms for these problems as well as some approaches to proving hardness in restricted computational models.

Amin Coja-Oghlan: An introduction to random constraint satisfaction problems

Random constraint satisfaction problems play an important role in computer science, discrete mathematics and related areas. This lecture gives an overview of the subject and points out the connections to statistical physics that have emerged since the early 2000s.

Amin Coja-Oghlan: Boltzmann distributions

A key element of the analysis of (random) constraint satisfaction problems is the understanding of certain probability distributions that they induce, called Boltzmann distributions. This lecture provides a modern perspective on the subject and introduces concepts such as replica symmetry breaking, reconstruction and pure states.

Amin Coja-Oghlan: Factor graphs and Belief Propagation

Belief Propagation is the fundamental tool of the modern study of random constraint satisfaction problems and also plays a role in many other areas, particularly modern coding theory. This lecture gives an introduction to Belief Propagation and its connection to the structure of the Boltzmann distribution.

Amin Coja-Oghlan: Condensation and quiet planting

At the condensation phase transition the Boltzmann distribution of a random constraint satisfaction problem undergoes a fundamental change and extensive correlations start to occur, a phenomenon called replica symmetry breaking in physics. In this lecture we see how the condensation phase transition can be pinned down rigorously.

Daniel Stefankovic: Spin models on trees and random regular graphs

When is sampling from a distribution given by a spin model (for example, hard-core model or Ising model) on a class of graphs easy (that is, when does there exists a polynomial-time sampling algorithm)? Motivated by this question we will look at the behavior of spin systems on trees (tree recursions, weak spatial mixing, strong spatial mixing).

Daniel Stefankovic: Spin models on trees and random regular graphs

When is sampling from a distribution given by a spin model (for example, hard-core model or Ising model) on a class of graphs easy (that is, when does there exists a polynomial-time sampling algorithm)? Motivated by this question we will look at the correlation decay technique (for regular trees and trees with bounded connective constant).

Daniel Stefankovic: Spin models on trees and random regular graphs

When is sampling from a distribution given by a spin model (for example, hard-core model or Ising model) on a class of graphs easy (that is, when does there exists a polynomial-time sampling algorithm)? Motivated by this question we will look at the behavior of spin systems on random regular and random regularbipartite graphs.

Daniel Stefankovic: Spin models on trees and random regular graphs

When is sampling from a distribution given by a spin model (for example, hard-core model or Ising model) on a class of graphs easy (that is, when does there exists a polynomial-time sampling algorithm)? Motivated by this question we will look at the connection between the behavior of spin systems on trees and their behavior on regular graphs, and how one uses random regular bipartite graphs as gadgets in hardness proofs.