Thursday 1-4, WB119
Note: I intend for the lectures to usually last
roughly 2 hours.
Grading scheme: TBA
Text: No required text, but “Random Graphs” by Bollobas, “Random Graphs” by Janson, Luczak and Rucinski, "Information, Physics and Computation" by Mezard and Montanari, and "The Nature of Computation" by Moore and Mertens are recommended.
Assignments
Assignment 1 is due Thur, Oct 2.
(Edited on Sept 26 - I corrected a typo in the definition
of a bicycle.)
Readings
Survey Papers:
Lecture 9
Algorithmic
barriers from phase transitions, Achlioptas
&
Coja-Oghlan
Gibbs
states and the set of solutions of
random constraint satisfaction
problems, Krzakala,
Montanari, Ricci-Tersenghi,
Semerjian & Zdeborová
Phase
transitions in the coloring of random
graphs, Krzakala
& Zdeborová
Lecture
10
The
random K-satisfiability problem: from
an analytic solution to an efficient
algorithm, Mezard & Zecchina
Survey
propagation an algorithm for
satisfiability, Braunstein, Mezard
& Zecchina
Lecture
11
The
freezing threshold for k-colourings of
a random graph, Molloy
The
condensation transition in random
hypergraph 2-coloring, Coja-Oghlan
& Zdeborová
Catching
the k-NAE-SAT threshold,
Coja-Oghlan & Panagiotou
Lecture 12
Going
after the k-SAT threshold,
Coja-Oghlan & Panagiotou
The
asymptotic k-SAT threshold,
Coja-Oghlan & Panagiotou
Proof
of the satisfiability conjecture for
large k, Ding, Sly & Sun
Bounds
for diluted mean-fields spin glass
models,
Panchenko & Talagrand
Replica bounds
for optimization problems and diluted spin systems,
Franz & Leone