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}lo{g}^{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 $\Omega (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(nlo{g}^{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\in X$ and a $y\in Y$ so that their concatenation $x\circ y$ is not dominated by any $z\in Z$, where vector $u$ is dominated by vector $v$ if $u_i\le v_i$ for each coordinate $1\le i\le d)$, and determine it as the "unique" candidate to be complete for this class (under fine-grained assumptions).