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.