The Goal of this Project
The goal of the project is to study the structural properties of geometric SAT instances and compare them to those of real-world instances. This could be done in several ways:
1. Obtaining bounds on the total variation distance between the geometric random k-SAT distribution and some basic/non-geometric generation procedure, such as uniform random connection.
2. Developing (with proof) a statistical test for whether a given instance has underlying geometry. Possible test statistics could include degree distribution, clustering coefficient, diameter, and so on.
3. Experimentally finding a test statistic for differentiating between real-world SAT instances and geometric random k-SAT instances; for recent examples, see [1, 3].
It would also be interesting to understand how any of these analyses depend on the dimension of the geometric space.