The Fine-Grained Complexity of Multi-Dimensional Ordering Properties

We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogonal range search, model-checking first-order properties on geometric intersection graphs, and elementary questions on multidimensional data like verifying Pareto optimality of a choice of data points.
Focusing on constant dimension d, we show that any $k$-quantifier, $d$-dimensional such problem is solvable in $O(n^{k-1} log^{d-1} n)$ time. Furthermore, this algorithm is conditionally tight up to subpolynomial factors: we show that assuming the 3-uniform hyperclique hypothesis, there is a $k$-quantifier, $(3k-3)$-dimensional problem in this class that requires time $Ω(n^{k-1-o(1)})$.
Towards identifying a single representative problem for this class, we study the existence of complete problems for the 3-quantifier setting (since 2-quantifier problems can already be solved in near-linear time $O(nlog^{d-1} n)$, and $k$-quantifier problems with $k > 3$ reduce to the $3$-quantifier case). ... mehrWe define a problem Vector Concatenated Non-Domination VCND_d (Given three sets of vectors $X$,$Y$ and $Z$ of dimension $d$,$d$ and $2d$, respectively, is there an $x ∈ X$ and a $y ∈ Y$ so that their concatenation $x∘y$ is not dominated by any $z ∈ Z$, where vector $u$ is dominated by vector $v$ if $u_i ≤ v_i$ for each coordinate $1 ≤ i ≤ d)$, and determine it as the "unique" candidate to be complete for this class (under fine-grained assumptions).