The class will continue to meet on Tuesdays at 4:00. We were unable to change the time to Thursday.
ROOM CHANGE!!! We are now meeting in UC 175, a somewhat bigger room.
Assignment 1 is due Tuesday Feb 24.
A few papers:
A survey paper on thresholds for colourability and satisfiablilty. Here's a section that I ended up deleting from the final version. (As a result, it is still in pre-polished form.)
Achlioptas and Naor's paper on the two possible values of the chromatic number.
A survey paper on lower bounds for the satisfiability threshold.
Achlioptas and Moore's paper and Achlioptas and Peres' paper on the asymptotic value of the k-SAT threshold.
My paper where I discuss some models of random CSP. It also includes watered down versions of Friedgut's theorem and Bourgain's theorem.
My paper on determining the threshold for k-cores and similar objects.
My first and second paper with Achlioptas and Beame on resolution based algorithms where the clause-density is below the satisfiability threshold.