Cristopher Moore, Santa Fe Institute, USA

Physics, Computation, Phase Transitions, and Networks (13.5h)

1. Computational Complexity: P vs. NP and NP-completeness

2. Random graphs, branching processes, and the giant component

3. Phase transitions in Satisfiability and Colorability, and simple rigorous bounds

4. Belief propagation and survey propagation in Satisfiability

5. The stochastic block model of networks, belief propagation, and the Bethe free energy

6. The detectability transition, spectral methods, and the non-backtracking matrix

7. EM algorithms, variational methods, and parameter learning

8. Poisson factorization, topic modeling, and mixed-membership block models

9. Further directions