Thursday 3-5, GB119
Grading scheme: Assignments – 50%, Project – 50%
Text: No required text, but “Random Graphs” by Bollobas and “Random Graphs” by Janson, Luczak and Rucinski are recommended.
Assignment 1 is due on Wed Feb 9.
Assignment 2 is due on Mon Mar 28. (I reposted a version with corrections.)
An ungraded exercise to be completed before the Mar 17 lecture.
Another ungraded exercise to be completed before the Mar 31 lecture.
Course Projects will be presented on Mon May 2 in GB 221:
1:10 Arron The
diameter of a scale-free random graph
2:25 Wesley Random MAX k-SAT: phase transitions in problems with real-valued (i.e.
non-binary) objective functions
3:40 Giovanna (2+p)-SAT
-----------------
Here are some papers that we discussed in class:
Friedgut Sharp Thresholds of Graph Properties, and the k-sat Problem.
Achlioptas and Friedgut A Sharp Threshold for k-Colorability
Hatami A structure theorem for Boolean functions with small total influences
Molloy and Reed A Critical Point for Random Graphs with a Given Degree Sequence.
Molloy and Reed The Size of the Largest Component of a Random Graph on a Fixed Degree Sequence.
Pittel, Spencer and Wormald Sudden emergence of a giant k-core in a random graph
Molloy Cores in random hypergraphs and boolean formulas
Fernholz and Ramachandran The giant k-core of a random graph with a specified degree sequence.
Achlioptas Lower Bounds for Random 3-SAT via Differential Equations
Wormald, The differential equation method for random graph processes and greedy algorithms
Chvatal and Szemeredi Many hard examples for resolution
Achlioptas, Beame and Molloy A Sharp Threshold in Proof Complexity Yields a Lower Bound for Satisfiability Search
Dubois and Mandler. The 3-XOR-SAT Threshold.
Achlioptas and Moore Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold
Achlioptas and Peres The Threshold for Random k-SAT is 2k log 2 - O(k)
Achlioptas and Naor The Two Possible Values of the Chromatic Number of a Random Graph
Achlioptas Random Satisfiability
Achlioptas Solution clustering in Random Satisfiability
Achlioptas, Coja-Oghlan and Ricci-Tersenghi On the solution-space geometry of random constraint satisfaction problems
Achlioptas and Coja-Oghlan Algorithmic Barriers from Phase Transitions
Braunstein, Mezard and Zecchina Survey Propagation: an algorithm for satisfiability
Maneva, Mossel and Wainwright A new look at survey propagation and its generalizations
Coja-Oghlan and Pachon-Pinzen The decimation process in random k-SAT
Coja-Oghlan A better algorithm for random k-SAT
Achlioptas and Ricci-Tersenghi Random formulas have frozen variables