Fall 2015

Orthogonal Vectors is Hard for First-Order Properties on Sparse Graphs

Thursday, December 3rd, 2015 4:30 pm4:55 pm

Add to Calendar

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.