Theory Seminar, Friday 22nd, 2:00pm
Warren Weaver Hall, Room 1314

Random k-SAT and the Power of Two Choices
 
Will Perkins, Georgia Tech

Random k-SAT is a distribution over instances of the NP-hard k-SAT problem. While it is known that it exhibits a sharp transition from satisfiability to unsatisfiability as the density of clauses increases, many details of this transition are still unknown. I will describe an Achlioptas-process version of the random k-SAT process: a bounded number of k-CNF clauses are drawn uniformly at random at each step, and exactly one added to the growing formula according to a particular rule. I will then prove the existence of a rule that shifts the satisfiability threshold. This extends a well-studied area of random graphs to random CSP's. In particular, while a rule to delay the 2-SAT threshold was known previously, this is the first proof of a rule to shift the threshold of a CSP that is NP-hard.