Abstract
The k-Orthogonal Vectors problem defined on sparse structures is a special case of model checking for (k + 1)-quantifier first-order sentences. Under Strong Exponential Time Hypothesis (SETH), it requires time Ω ̃(m^k). This paper shows k-Orthogonal Vectors defined on sparse structures is complete in the model checking problems of sentences quantified by k existential quantifiers and one universal quantifier, under probabilistic reductions. Moreover, if any one of the 2-Orthogonal Vectors, Sperner Family and 2-Set Covering problems is decidable in subquadratic time, then model checking of any first-order sentence with (k + 1) ≥ 3 quantifiers will have O(m^{k−ε}) probabilistic algorithms for some ε > 0.
Joint work with Russell Impagliazzo.