MATH Seminar

Title: Thresholds for Random Geometric k-SAT
Seminar: Combinatorics
Speaker: Will Perkins of Georgia Tech
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2013-11-08 at 4:00PM
Venue: W306
Download Flyer
Abstract: Random $k-SAT$ is a distribution over boolean formulas studied widely in combinatorics, 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. 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 and the random geometric graph.