Georgia Institute of Technology College of Sciences

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.