Thresholds for Random Geometric k-SAT

Stochastics Seminar
Thursday, October 24, 2013 - 3:05pm
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech, School of Mathematics
Random k-SAT is a distribution over boolean formulas studied widely in both statistical physics and theoretical computer science for its intriguing behavior at its phase transition.  I will present results on the satisfiability threshold in a geometric model of random k-SAT: labeled boolean literals are placed uniformly at random in a d-dimensional cube, and for each set of k contained in a ball of radius r, a k-clause is added to the random formula.  Unlike standard random k-SAT, this model exhibits dependence between the clauses.  For all k we show that the satisfiability threshold is sharp, and for k=2 we find the location of the threshold as well.  I will also discuss connections between this model, the random geometric graph, and other probabilistic models.  This is based on joint work with Milan Bradonjic.