July 17-21, 2017

Lipschitz Hall, Endenicher Allee 60

Organizer: Joe Neeman

Description:

Constraint satisfaction problems such as graph coloring and boolean satisfiability are fundamental for understanding computational complexity and certain physical processes. Randomly generated instances of these problems are known to have intricate probabilistic structure, and recent work has made good progress in uncovering this structure.

This Hausdorff school is intended for motivated graduate and postdoctoral students who want to get acquainted with this area, its new developments, and the new probabilistic tools that led to them.

Lecture Series by: 

• Amin Coja-Oghlan (Goethe University)
  
  • An introduction to random constraint satisfaction problems
  • Boltzmann distributions
  • Factor graphs and Belief Propagation
  • Condensation and quiet planting
• Cristopher Moore (Santa Fe Institute)
  
  • Classic Bounds on the k-SAT Threshold
  • Community detection and the stochastic block model: belief propagation and the Kesten-Stigum threshold
  • Information-theoretic thresholds on the block model: the second moment method and contiguity
  • The conjectured hard regime and open questions
• Daniel Stefankovic (University of Rochester)
  
  • Spin models on trees and random regular graphs I
  • Spin models on trees and random regular graphs II
  • Spin models on trees and random regular graphs III
• Mihyun Kang (Graz University of Technology)
  • Core forging and local limit theorems for the k-core of random graphs
• Will Perkins
  • Planted satisfiability and refutation: algorithms and barriers