Cris Moore: The Nature of Computation

1. P, NP-completeness, and all that

I'll discuss polynomial-time algorithms, and the notion of NP-completeness, with a focus on statistical physics. For instance, finding the ground state of a spin glass is hard, but finding the ground state of a ferromagnetic Ising model with external fields is easy. I'll explain that "hard" here means "hard unless thousands of other problems are much easier than we think", including the problem of finding proofs of unsolved mathematical problems.

2. Phase transitions in random graphs

I'll discuss the most basic phase transition in computer science: the emergence of a giant component in Erdos-Renyi random graphs. I'll show how to locate the transition, and compute the size of the giant component, using branching processes. If time permits I'll discuss the k-core transition as well.

3. Random k-SAT and the satisfiability transition

I'll discuss random k-SAT and upper and lower bounds on the critical density at which formulas become unsatisfiable, including algorithmic lower bounds using the method of differential equations and upper bounds using the first moment method. I'll describe the second moment method, why it works for NAESAT but not for SAT, and how to fix it. I'll end with a preview of Coja-Oghlan's talks, including the clustering transition where the set of solutions breaks apart into clusters that are separated by large energy barriers, and how we think this is related to the hardness of the problem.

4. The stochastic block model, message passing, and community structure in networks

The stochastic block model is a popular model for network structure, which has been applied in sociology, biology, and many other fields. Each node in the network belongs to a community, but these memberships are hidden from us, and we want to infer them from the topology. I'll discuss a recent algorithm (joint work with Decelle, Krzakala, and Zdeborova) that uses belief propagation and the cavity method to do this, and also how this algorithm reveals a phase transition in the detectability of communities.

5. Markov chains and mixing times

I'll discuss the theory of Markov chains and mixing times --- how to prove -- --rigorous bounds on the time it takes Glauber dynamics, for instance, to find a nearly-random coloring of a graph. I'll sketch why temporal mixing and spatial mixing (the decay of correlations, and Gibbs uniqueness) are closely related.