CSC 2427: Random Constraint Satisfaction Problems, Fall 2014

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.

Course Description

Previous Lectures

Assignments


Assignment 1 is due Thur, Oct 2(Edited on Sept 26 - I corrected a typo in the definition of a bicycle.)

Assignment 2 is due Thur, Nov 27.  - I'll accept late assignments until Mon Dec 1.

Readings

Survey Papers:

Random Satisfiability, Achlioptas
Random Constraint Satisfaction Problems, Coja-Oghlan


Lecture 3:

Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold, Achlioptas & Moore
The Threshold for Random k-SAT is 2k log 2 - O(k), Achlioptas & Peres
The Two Possible Values of the Chromatic Number of a Random Graph, Achlioptas & Naor

Lecture 4:

Sharp Thresholds of Graph Properties, and the k-SAT problem, Friedgut
A Sharp Threshold for k-Colorability,
  Achlioptas&Friedgut
Hunting for Sharp Thresholds, Friedgut

Lecture 5:

Lower Bounds for Random 3-SAT via Differential Equations
, Achlioptas
A better algorithm for random k-SAT, Coja-Oghlan
The differential equation method for random graph processes and greedy algorithms, Wormald


Lecture 6:

A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, Bollobas
Sudden emergence of a giant k-core in a random graph,  Pittel, Spencer & Wormald
Cores in random hypergraphs and boolean formulas, Molloy

The 3-XORSAT threshold, Dubois & Mandler

Tight thresholds for cuckoo hashing via XORSAT,
Dietzfelbinger, Goerdt, Mitzenmacher, Montanari, Pagh & Rink
The satisfiability threshold for k-XORSAT, Pittel&Sorkin

Lecture 7

The set of solutions for random XORSAT formulae,
Ibrahimi, Kanoria, Kraning & Montanari
The solution space geometry of random linear equations,
Achlioptas & Molloy
Two solutions to diluted p-spin models and XORSAT problems,
Mézard, Ricci-Tersenghi & Zecchina
On the freezing of var
iables in random constraint satisfaction problems, Semerjian

Lecture 8

Random formulas have frozen variables,
Achlioptas, Coja-Oghlan & Ricci-Tersenghi
On the solution-space geometry of random constaint satisfaction problems,
Achlioptas, Coja-Oghlan & Ricci-Tersenghi

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