Thresholds for Random Geometric k-SAT.
Milan Bradonjić, Will Perkins · arXiv (Cornell University) · 2013
We study two geometric models of random k-satisfiability which combine random k-SAT with the Random Geometric Graph: boolean literals are placed uniformly at random or according to a Poisson process in a cube, and for each set of k literals contained in a ball of a given radius, a clause is formed. For k = 2 we find the exact location of the satisfiability threshold (as either the radius or intensity of the Poisson process varies) and show the threshold is sharp; for k ≥ 3 we give bounds on the threshold that differ by a constant factor; and for one of the two models we prove that the threshold is in fact sharp for all k ≥ 2. 1