Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k+1 quantifiers takes time $O(m^k)$ and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require $O(m^{k-\epsilon})$ time for any $\epsilon > 0$. (Here, m represents the size of the input structure, i.e. the number of tuples in all relations.)

We give algorithms for every first-order property that improves this upper bound to $m^k/2^{\Theta(\sqrt{\log n})}$, i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. Moreover, we show that further improvement is equivalent to improving algorithms for sparse instances of the well-studied Orthogonal Vectors problem. Surprisingly, both results are obtained by showing completeness of the Sparse Orthogonal Vectors problem for the class of first-order properties under fine-grained reductions. To obtain improved algorithms, we apply the fast Orthogonal Vectors algorithm of [AWY15,CW16].

While fine-grained reductions (reductions that closely preserve the conjectured complexities of problems) have been used to relate the hardness of disparate specific problems both within P and beyond, this is the first such completeness result for a standard complexity class.

Made updates according to the valuable comments from the Transactions on Algorithms reviewers.

Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k+1 quantifiers takes time $O(m^k)$ and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require $O(m^{k-\epsilon})$ time for any $\epsilon > 0$. (Here, m represents the size of the input structure, i.e. the number of tuples in all relations.)

We give algorithms for every first-order property that improves this upper bound to $m^k/2^{\Theta(\sqrt{\log n})}$, i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. Moreover, we show that further improvement is equivalent to improving algorithms for sparse instances of the well-studied Orthogonal Vectors problem. Surprisingly, both results are obtained by showing completeness of the Sparse Orthogonal Vectors problem for the class of first-order properties under fine-grained reductions. To obtain improved algorithms, we apply the fast Orthogonal Vectors algorithm of [AWY15,CW16].

While fine-grained reductions (reductions that closely preserve the conjectured complexities of problems) have been used to relate the hardness of disparate specific problems both within P and beyond, this is the first such completeness result for a standard complexity class.

(1) Algorithmic applications: Our reduction from first-order properties to OV gives better algorithms for first-order properties.

(2) Extending the result to hypergraphs (relations of arity greater than 2).

(3) The new reduction algorithm is deterministic.

(4) We are glad that Antonina Kolokolova and Ryan Williams became our coauthors.

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until now, there have been few equivalences between problems and in particular, no problems that were complete for natural classes under fine-grained reductions. We give the first such completeness results. We consider the class of first-order graph property problems, viewing the input in adjacency list format (aka "sparse graph representation"). For this class, we show that the sparse Orthogonal Vectors problem is complete under randomized fine-grained reductions. In proving completeness for this problem, we also show that this sparse problem is equivalent to the standard Orthogonal Vectors problem when the number of dimensions is polynomially related to the number of vectors. Finally, we also establish a completeness and hardness result for k-Orthogonal Vectors.

Our results imply that the conjecture "not every first-order graph problem has an improved algorithm" is a useful intermediary between SETH and the conjectured hardness of problems such as Edit Distance. It follows that, if Edit Distance has a substantially subquadratic algorithm, then every first order graph problem has an improved algorithm. On the other hand, if first order graph property problems have improved algorithms, this falsifies SETH (and even some weaker versions of SETH) and gives new circuit lower bounds. We hope that this is the beginning of extending fine-grained complexity to include classes of problems as well as individual problems.

Updated the k=2 case in Section 5, "Step 1-2".

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until now, there have been few equivalences between problems and in particular, no problems that were complete for natural classes under fine-grained reductions. We give the first such completeness results. We consider the class of first-order graph property problems, viewing the input in adjacency list format (aka "sparse graph representation"). For this class, we show that the sparse Orthogonal Vectors problem is complete under randomized fine-grained reductions. In proving completeness for this problem, we also show that this sparse problem is equivalent to the standard Orthogonal Vectors problem when the number of dimensions is polynomially related to the number of vectors. Finally, we also establish a completeness and hardness result for k-Orthogonal Vectors.

Our results imply that the conjecture "not every first-order graph problem has an improved algorithm" is a useful intermediary between SETH and the conjectured hardness of problems such as Edit Distance. It follows that, if Edit Distance has a substantially subquadratic algorithm, then every first order graph problem has an improved algorithm. On the other hand, if first order graph property problems have improved algorithms, this falsifies SETH (and even some weaker versions of SETH) and gives new circuit lower bounds. We hope that this is the beginning of extending fine-grained complexity to include classes of problems as well as individual problems.