Random k-SAT and the Power of Two Choices

Combinatorics Seminar
Friday, September 7, 2012 - 15:05
1 hour (actually 50 minutes)
Skiles 005
School of Mathematics, Georgia Tech
We study 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. We prove the existence of a rule that shifts the satisfiability threshold. This extends a well-studied area of probabilistic combinatorics and 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. We then propose a gap decision problem based upon this semi-random model with the aim of investigating the hardness of the random k-SAT decision problem.