Universität Bonn

Hausdorff School: "Random Constraint Satisfaction"

July 17-21, 2017

Lipschitz Hall, Endenicher Allee 60

Organizer: Joe Neeman



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


Period of stay
Jess Banks University of California-Berkeley 10.07.2017 – 22.07.2017
Chris Brzuska TU Hamburg 16.07.2017 – 21.07.2017
Zongchen Chen Georgia Institute of Technology 16.07.2017 – 22.07.2017
Amin Coja-Oghlan Goethe University 16.07.2017 – 21.07.2017
Nicola Del Giudice Graz University of Technology (TU Graz) 16.07.2017 – 22.07.2017
Matthew Fahrbach Georgia Institute of Technology 16.07.2017 – 22.07.2017
Lennart Gulikers Inria-Microsoft Joint Research Centre 16.07.2017 – 22.07.2017
Falko Hegerfeld Universität Bonn 17.07.2017 – 21.07.2017
Mihyun Kang Graz University of Technology 16.07.2017 – 19.07.2017
Tobias Kapetanopoulos Goethe University Frankfurt am Main 16.07.2017 – 21.07.2017
Cristopher Moore Santa Fe Institute 16.07.2017 – 21.07.2017
Noela Müller Goethe University Frankfurt 16.07.2017 – 21.07.2017
Will Perkins University of Birmingham 19.07.2017 – 21.07.2017
Daniel Stefankovic University of Rochester 17.07.2017 – 21.07.2017
Anastasiya Tanana Universität Bonn 17.07.2017 – 21.07.2017
Kingsley King On Yung The Chinese University of Hong Kong 16.07.2017 – 22.07.2017
Wird geladen