(Multivariate) $𝒌$-SUM as Barrier to Succinct Computation

Consider the problem Selection: Given $X\subseteq \mathbb{Z}$ and $1\le k\le N$, return the $k$-th largest element in $X$. Selection is well known to be solvable in time $O(N)$; see [8, 15]. Its succinct version succinct-Selection has received considerable attention as well [30, 29, 28, 19] and can be solved significantly faster than decompress-and-solve, specifically, in time $\tilde{O}(n)$.²²2The authors consider a slight variant in which $A+B$ is viewed as a multiset (or $|A+B|=|A|\cdot |B|$).

Consider the problem of skyline computation (aka non-dominance filtering or Pareto front computation), see, e.g. [32, 14, 22]: Given $X\subseteq {\mathbb{Z}}^d$, compute the set $Z$ of non-dominated points, i.e., all $x\in X$ for which there is no $x^{\prime }\in X$ with $x^{\prime }\ne x$ and $x\le x^{\prime }$ component-wise. This problem can be solved in near-linear time $\tilde{O}(N)$, see, e.g., [32]. Its succinct version is known as Pareto Sum and naturally occurs in several multi-objective optimization algorithms, see Hespe et al. [27]. Notably, a conditional lower bound of $N^{1-o(1)}$ that holds when the output size is $\mathrm{\Theta }(\sqrt{N})$ has been proven under the $(\min ,+)$-convolution hypothesis [21] and the 3-SUM hypothesis [24]. We shall investigate this problem in much more detail below.

The $3$-SUM problem³³3Given sets $A,B,C$ do there exist $a\in A,b\in B,c\in C$ s.t $a+b+c=0$. is one of the first problems used for conditional lower bounds. Initially introduced to explain various quadratic-time barriers observed in computational geometry [23], it has since been used to show quadratic-time hardness for a wealth of problems from various fields [41, 35, 5, 34, 13]. Its generalization, the $k$-SUM problem⁴⁴4The $k$-SUM problem asks, given sets $A_1,\mathrm{\dots },A_k$ of $n$ numbers, whether there exist $a_1\in A_1,\mathrm{\dots },a_k\in A_k$ such that ${\sum }_{i=1}^k{a}_i=0$. The $k$-SUM hypothesis states that for no $ϵ>0$ there exists a $O(n^{\lceil k/2\rceil -ϵ})$ time algorithm that solves $k$-SUM., has led to further conditional lower bounds beyond quadratic-time solvable problems [18, 4, 1, 2]. For a more comprehensive overview, we refer to the survey of Williams [43].

An important aspect of our investigations is that we establish fine-grained equivalences with $k$-SUM problems, which requires the somewhat unusual direction of reducing certain problems to $k$-SUM. Conveniently, we may exploit for this task a recent completeness theorem [24]: This work introduces general classes of problems which can be reduced to $k$-SUM, thereby simplifying the arguments needed to reduce sumset-related problems to $k$-SUM. Specifically, we shall need the existential fragment of the class ${\mathrm{𝖥𝖮𝖯}}_{\mathbb{Z}}$: It consists of problems whose inputs are sets $A_1\subseteq {\mathbb{Z}}^{d_1},\mathrm{\dots },A_k\subseteq {\mathbb{Z}}^{d_k}$, and free variables $t_1\mathrm{\dots }{t}_{\mathrm{\ell }}\in \mathbb{Z}$, and the task is to determine whether there exist $a_1\in A_1\mathrm{\dots }{a}_k\in A_k$ such that $\phi (a_1[1],\mathrm{\dots },a_1[d_1],\mathrm{\dots },a_k[1],\mathrm{\dots },a_k[d_k],t_1\mathrm{\dots },t_{\mathrm{\ell }})$ holds, where $\phi$ is a fixed, but arbitrary linear arithmetic formula over the vector entries of $a_1\mathrm{\dots }{a}_k$ and the free variables. (In particular, the dimensions $d_1,\mathrm{\dots },d_k$ are constant.) Each such problem is near-linear time reducible to $k$-SUM. We will frequently argue in our reductions that subtasks can be expressed as an existential ${\mathrm{𝖥𝖮𝖯}}_{\mathbb{Z}}$ formula and exploit the completeness theorem.

The authors in [9] explored connections of the $X+Y$ sorting problem with the $(\min ,+)$-convolution problem. Other works consider the fine-grained complexity of other notions of succinct inputs, such as representing sequences succinctly as grammar-based compressions [2, 1], or succinctly defined graphs using the notion of factored graphs [25].

For context, we observe that there is a large number of non-trivial geometric primitives (beyond selection) for which fast succinct computation is indeed possible.

As perhaps most prominent and well-known example, consider the convex hull problem: Given $A,B\subseteq {\mathbb{Z}}^2$, compute the convex hull $\mathrm{𝖼𝗈𝗇𝗏}(X)$ of $X=A+B$. By a folklore identity, $\mathrm{𝖼𝗈𝗇𝗏}(A+B)=\mathrm{𝖼𝗈𝗇𝗏}(A)+\mathrm{𝖼𝗈𝗇𝗏}(B)$, with complexity $|\mathrm{𝖼𝗈𝗇𝗏}(A)|+|\mathrm{𝖼𝗈𝗇𝗏}(B)|$. This yields $\tilde{O}(n)$-time algorithms for succinctly computing convex hulls, see also [17]. This fact leads us to the following general observation.

While the observation is simple, it leads to an interesting class of problems which can be solved in near-linear time in the size of the sumset compression. Some examples of problems which can be efficiently solved using only the convex hull of the input are the diameter of points, the maximum bounding box, the distance between two convex hulls and many more, described by Shamos in [36]. All these problems can be solved with a known technique originally introduced by Shamos [37, 36], which has subsequently been coined rotating calipers and further explored by Toussaint [39].

Consider the problem Closest $L_{\mathrm{\infty }}$-Pair: Given $X\subseteq {\mathbb{Z}}^d$, determine ${\min }_{x_1,x_2\in X,x_1\ne x_2}{\Vert x_1-x_2\Vert }_{\mathrm{\infty }}$. Its natural maximization analogue is Furthest $L_{\mathrm{\infty }}$-Pair: Given $X\subseteq {\mathbb{Z}}^d$, determine ${\max }_{x_1,x_2\in X}{\Vert x_1-x_2\Vert }_{\mathrm{\infty }}$. Both problems are solvable in near-linear time $\tilde{O}(N)$ whenever $d$ is constant [22, 10].

However, we observe that the succinct versions differ substantially in their time complexity: Succinct-Furthest $L_{\mathrm{\infty }}$-Pair can be solved in time $\tilde{O}(n)$, while for succinct-Closest $L_{\mathrm{\infty }}$-Pair we obtain a 3-SUM-based lower bound of $N^{1-o(1)}$ already in 1D, using the fact that the EqDist problem is 3-SUM-hard [6]; see the full version of the paper.

Naturally, we may also consider the bichromatic case of the Closest $L_{\mathrm{\infty }}$-Pair problem: Given $X,Y\subseteq {\mathbb{Z}}^d$, determine ${\min }_{x\in X,y\in Y}{\Vert x-y\Vert }_{\mathrm{\infty }}$. Here, the natural succinct version receives sets $A,B,C,D\subseteq {\mathbb{Z}}^d$ as inputs, and the task is to solve the problem for $X=A+B$ and $Y=C+D$. We prove that this succinct-Bichromatic $L_{\mathrm{\infty }}$-Pair problem is fine-grained equivalent to 4-SUM. The reduction to 4-SUM follows from observing that the decision problem can be formulated as an existential ${\mathrm{𝖥𝖮𝖯}}_{\mathbb{Z}}$ formula, which can be reduced to 4-SUM [24]. It remains an interesting question whether the monochromatic succinct Closest-$L_{\mathrm{\infty }}$-Pair is fine-grained equivalent to 3-SUM (our results place it between 3-SUM and 4-SUM). For further fine-grained complexity results on Closest and Furthest Pair in higher dimensions; see e.g., [42] and [31].

The remaining problems that we study will exhibit a tight connection to a multivariate version of the $3$-SUM problem. Specifically, we introduce the following problem:

It is easy to see that this problem can be solved in time $\tilde{O}(\min \{kn,n^2+k\})$: The $O(kn)$ bound follows by solving, for each $c\in C$, the corresponding 2-SUM problem of detecting $a\in A,b\in B$ with $a+b=c$, which is well-known to be solvable in time $O(n)$. The $\tilde{O}(n^2+k)$ upper bound follows from computing $A+B$ explicitly, and solving the corresponding dictionary problem for each $c\in C$. This time bound turns out to be conditionally tight; see Section 3: For any $k=\mathrm{\Theta }(n^{\alpha })$ with , we show using standard techniques that this problem cannot be solved in time $O({(nk)}^{1-ϵ})$ with $ϵ>0$ unless the 3-SUM hypothesis is false. Note that this establishes a conditionally tight answer for all $k$: If $k=\mathrm{\Theta }(n^{\alpha })$ with $\alpha >1$, then we obtain a $n^{2-o(1)}$ conditional lower bound via padding, and a $\mathrm{\Omega }(k)$ lower bound follows from the input size of the problem.

Perhaps surprisingly, this problem naturally captures the precise fine-grained complexity of various succinct geometric primitives. Note that when $k=n$, All-ints 3-SUM$(n,n,k)$ is well known to be subquadratic equivalent to 3-SUM [40], but a fine-grained equivalence for $k=\mathrm{\Theta }(n^{\alpha })$ with does not appear to follow from standard techniques. We will thus make use of a slight generalization of the completeness theorem for existential ${\mathrm{𝖥𝖮𝖯}}_{\mathbb{Z}}$ formulas, which is implicit in [24]. Consider the following problems: Given $A\subseteq {\mathbb{Z}}^{d_1},B\subseteq {\mathbb{Z}}^{d_2},C\subseteq {\mathbb{Z}}^{d_3}$ of sizes $n$, $n$ and $k$, respectively, compute for each $c\in C$, whether there exist $a\in A,b\in B$ such that a linear arithmetic formula $\phi (a[1],\mathrm{\dots },a[d_1],b[1],\mathrm{\dots },b[d_2],c[1],\mathrm{\dots },c[d_3])$ over the entries in the vectors $a,b,c$ holds. For every linear arithmetic formula $\phi$, we can reduce this problem to $\tilde{O}(1)$ instances of All-ints $3$-SUM$(n,n,k)$. A standalone proof of this fact can be found in the full version of the paper.

Consider a batched (or offline) version of answering orthogonal range queries over $X$, which we call Batched Orthogonal Range Searching: Given $X\subseteq {\mathbb{Z}}^d$ and orthogonal ranges $r_1,\mathrm{\dots },r_k$, determine for each $j=1,\mathrm{\dots },k$ whether $X\cap r_j$ is empty. This problem can be solved in time $\tilde{O}(N+k)$ for constant $d$, see, e.g. [12]. We observe that succinct-Batched Orthogonal Range Searching is fine-grained equivalent to All-ints 3-SUM$(n,n,k)$. To reduce from All-ints 3-SUM$(n,n,k)$, use $A,B$ as succinct input sets for a 1-dimensional instance of succinct-Batched Orthogonal Range Searching and for $C=\{c_1,\mathrm{\dots },c_k\}$ choose $r_i=[c_i,c_i]$. The other direction follows from observing that we may represent the succinct Orthogonal Range Searching problem as a suitable All-ints-${\mathrm{𝖥𝖮𝖯}}_{\mathbb{Z}}$ formula. The details can be found in the full version of the paper.

Recall the prominent geometric problem of skyline computation (aka non-dominance filtering or maxima of point sets computation), see, e.g. [32, 14, 22]: Given $X\subseteq {\mathbb{Z}}^d$, compute the set $Z$ of non-dominated points, i.e., all $x\in X$ for which there is no $x^{\prime }\in X$ with $x^{\prime }\ne x$ and $x\le x^{\prime }$ component-wise. This (explicit) problem can be solved in time $O(N\log k)$ [32], where $k=|Z|$ denotes the output size. For $d=2$, Hespe et al. show how to compute its succinct variant, the Pareto Sum, in time $O(n\log n+kn)$. We prove that computing all $k$ non-dominated points of $X=A+B$ is fine-grained equivalent to All-ints 3-SUM$(n,n,k)$.

Starting point of our reduction from All-ints 3-SUM$(n,n,k)$ to the Pareto Sum is the subquadratic reduction from 3-SUM to Pareto Sum given in [24], which uses Conv3-SUM as an intermediate step. Notably, however, our multivariate setting poses a perhaps unexpected challenge: The standard reductions from 3-SUM to Conv3-SUM [35, 11] do not readily transfer to a multivariate setting. Instead, we introduce a variant of Conv3-SUM that we call All-ints-MixedConv3-SUM($n,n,k$)⁵⁵5The definition appears related in spirit (but different) to Factored $3$-SUM defined in [16].:

This problem can easily be solved in time $O(kn)$. We carefully adapt the reduction from 3-SUM to convolution 3-SUM given in [11] to reduce All-ints 3-SUM$(n,n,k)$ to All-ints-MixedConv3-SUM$(n,n,k)$. As a further technical challenge, our approach requires an equivalence between the problem of computing the complete Pareto Sum and computing the Pareto Sum inside a given query range. Specifically, in our lower bound, we need to allow as query ranges quadrants of the form $[x,\mathrm{\infty })\times [y,\mathrm{\infty })$; with this choice, even for sets $A,B$ with a Pareto Sum as large as $\mathrm{\Omega }(n^2)$ one may still give a query range with arbitrary small outputsize $k$, e.g., $k=O(1)$. Interestingly, using an involved construction detailed in Section 4.1, we show that this problem reduces to its specical case of computing the complete Pareto set under the promise that its size is $k+O(1)$. As a by-product, this also shows that for any $n\in \mathbb{N}$, there exist sets $A,B$ of size $n$ of incomparable vectors in ${\mathbb{Z}}^2$ with a Pareto Sum of constant size, which does not appear to have been proven before. After showing this equivalence, we reduce All-ints-MixedConv3-SUM to Pareto Sum, reminiscent of the reduction from Convolution 3-SUM to Pareto Sum in [24].

The reverse reduction from Pareto Sum to All-ints 3-SUM$(n,n,k)$ is also technically interesting: while Hespe et al. [27] show how to compute each of the $k$ output points successively in $\tilde{O}(n)$ time per point, unfortunately, we cannot follow this approach in our reduction (calling an All-ints 3-SUM$(n,n,k)$-oracle $\mathrm{\Omega }(k)$ times would trivially exceed $\tilde{O}(kn)$ running time). Instead, we aim to identify the $k$ output points essentially simultaneously. To this end, we perform a divide-and-conquer approach. We maintain a set of already identified Pareto Sum points $S$, as well as a list of up to $k$ active $x$-intervals – an interval is deemed active if it contains at least one (unidentified) point of the Pareto Sum. At each level of the recursion, we split all active intervals into two halves. The key observation is the following: Given $S$ and an arbitrary list of intervals $I_1,\mathrm{\dots },I_s$, we can compute for each $I_j$ whether it contains a point in the Pareto Sum (but not already in $S$) using only $\tilde{O}(1)$ All-ints ${\mathrm{𝖥𝖮𝖯}}_{\mathbb{Z}}$ $(n,n,s)$ queries, which in turn can be reduced to $\tilde{O}(1)$ All-ints 3-SUM$(n,n,k)$ instances. After $O(\log n)$ levels of the recursion, each interval consists of at most a single integer, and can be resolved fully. The details can be found in Section 4.

Consider the maximum independent set problem (MIS) in unit interval graphs: Given a set of (open) unit intervals $ℐ$ in $\mathbb{Z}$, compute a maximum independent set $S^{\ast }$, i.e., a pairwise non-intersecting subset of intervals maximizing its size. A simple greedy algorithm is well known to solve the problem in time $O(n\log n)$, see, e.g. [26]. Taking the output size $k=|S^{\ast }|$ into account, this can be slightly improved to time $O(n\log k)$, see [38].

For studying its connection with All-ints 3-SUM$(n,n,k)$, the technical work spent for the equivalence to Pareto Sum pays off: On the lower bound side, we establish a fine-grained reduction from All-ints 3-SUM$(n,n,k)$ to succinct-MIS in unit interval graphs using a similar approach as for the Pareto Sum. In particular, we may reduce immediately from All-ints MixedConv3-SUM$(n,n,k)$, and transfer conceptually similar arguments to the MIS setting.

On the upper bound side, we are not quite able to establish the reverse reduction. However, we show how to reduce computing a maximal independent set to All-ints 3-SUM$(n,n,k)$, again exploiting careful parallel binary searches in a divide-and-conquer approach. It remains an interesting open problem to reduce the MIS problem in unit interval graphs to All-ints 3-SUM$(n,n,k)$. The details can be found in the full version of the paper.

For the problems equivalent to All-ints 3-SUM$(n,n,k)$, our results show that improving over decompress-and-solve running time $N^{1\pm o(1)}$ is possible whenever the output size $k$ is small enough, specifically $k=O(N^{1/2-ϵ})=O(n^{1-ϵ})$ for some $ϵ>0$. We refer to Figure 1 for an overview of the reductions shown. In the full version of the paper, we provide a table which summarizes runtimes for various problems, when defined succinctly and explicitly.