Thresholds for Random Geometric k-SAT

Random k-SAT is a fundamental model in the study of random structures and theoretical computer science. The model exhibits a swift transition from almost certain satisfiability to almost certain unsatisfiability as the ratio of clauses to variables increases. Experimentally, instances near this threshold are computationally difficult. Like the Erd½os-R´enyi random graph G(n, p), the random k-SAT model lacks geometry. As the Random Geometric Graph introduced geometry into the context of random graphs, we introduce geometry to the satisfiability problem by introducing a geometric random k- SAT model. We investigate the transition from satisfiability to unsatisfiability in this model, proving bounds on the location of the transition and showing that the threshold is sharp.