Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic

Gokaj, Geri; Künnemann, Marvin

doi:10.4230/LIPIcs.ITCS.2025.55

Completeness Theorems for $k$ -SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic

Geri Gokaj

Karlsruhe Institute of Technology, Germany Marvin Künnemann Karlsruhe Institute of Technology, Germany

Abstract

In the last three decades, the $k$ -SUM hypothesis has emerged as a satisfying explanation of long-standing time barriers for a variety of algorithmic problems. Yet to this day, the literature knows of only few proven consequences of a refutation of this hypothesis. Taking a descriptive complexity viewpoint, we ask: What is the largest logically defined class of problems captured by the $k$ -SUM problem?

To this end, we introduce a class $\mathsf{FOP}_{\mathbb{Z}}$ of problems corresponding to deciding sentences in Presburger arithmetic/linear integer arithmetic over finite subsets of integers. We establish two large fragments for which the $k$ -SUM problem is complete under fine-grained reductions:

1.

The $k$ -SUM problem is complete for deciding the sentences with $k$ existential quantifiers.
2.

The $3$ -SUM problem is complete for all $3$ -quantifier sentences of $\mathsf{FOP}_{\mathbb{Z}}$ expressible using at most $3$ linear inequalities.

Specifically, a faster-than- $n^{\lceil k/2\rceil\pm o(1)}$ algorithm for $k$ -SUM (or faster-than- $n^{2\pm o(1)}$ algorithm for $3$ -SUM, respectively) directly translate to polynomial speedups of a general algorithm for all sentences in the respective fragment.

Observing a barrier for proving completeness of $3$ -SUM for the entire class $\mathsf{FOP}_{\mathbb{Z}}$ , we turn to the question which other – seemingly more general – problems are complete for $\mathsf{FOP}_{\mathbb{Z}}$ . In this direction, we establish $\mathsf{FOP}_{\mathbb{Z}}$ -completeness of the problem pair of Pareto Sum Verification and Hausdorff Distance under $n$ Translations under the $L_{\infty}$ / $L_{1}$ norm in $\mathbb{Z}^{d}$ . In particular, our results invite to investigate Pareto Sum Verification as a high-dimensional generalization of 3-SUM.

Keywords and phrases:

fine-grained complexity theory, descriptive complexity, presburger arithmetic, completeness results,

k

-SUM

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Complexity theory and logic

Acknowledgements:

The authors like to thank the reviewers for constructive feedback as well as Karl Bringmann and Nick Fischer for helpful discussions.

Funding:

This research is supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 462679611.

DOI:

10.4230/LIPIcs.ITCS.2025.55

Event:

16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Editors:

Raghu Meka

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Consider a basic question in complexity theory: How can we determine for which problems an essentially quadratic-time algorithm is best possible? If a given problem $A$ admits an algorithm running in $n^{2+o(1)}$ time, and it is known that $A$ cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon>0$ , then clearly the $n^{2+o(1)}$ algorithm has optimal runtime, up to subpolynomial factors. This question can be asked more generally for any $k\geq 1$ and time $n^{k\pm o(1)}$ . To this day, the theoretical computer science community is far from able to resolve this question unconditionally. However, a surge of results over recent years uses conditional lower bounds based on plausible hardness assumptions to shed some light on why some problems seemingly cannot be solved in time $O(n^{k-\epsilon})$ for any $\epsilon>0$ . Most notably, reductions from $k$ -OV, $k$ -SUM and the weighted $k$ -clique problem have been used to establish $n^{k-o(1)}$ -time conditional lower bounds, often matching known algorithms; see [50] for a detailed survey.

In this context, the $3$ -SUM hypothesis is arguably the first – and particularly central – hardness assumption for conditional lower bounds. Initially introduced to explain various quadratic-time barriers observed in computational geometry [35], it has since been used to show quadratic-time hardness for a wealth of problems from various fields [52, 46, 6, 40, 29, 3, 21]. Its generalization, the $k$ -SUM¹¹1The $k$ -SUM problem asks, given sets $A_{1},\dots,A_{k}$ of $n$ numbers, whether there exist $a_{1}\in A_{1},\dots,a_{k}\in A_{k}$ such that $\sum_{i=1}^{k}a_{i}=0$ . The $k$ -SUM hypothesis states that for no $\epsilon>0$ there exists a $O(n^{\lceil k/2\rceil-\epsilon})$ time algorithm that solves $k$ -SUM. hypothesis, has led to further conditional lower bounds beyond the quadratic-time regime [31, 4, 1, 2, 41]. For a more comprehensive overview, we refer to [50].

The centrality of the $3$ -SUM hypothesis for understanding quadratic-time barriers begs an interesting question: Does $3$ -SUM fully capture quadratic-time solvability, in the sense that it is hard for the entire class $\mathsf{DTIME}(n^{2})$ ? Alas, Bloch, Buss, and Goldsmith [10] give evidence that we are unlikely to prove this: If $3$ -SUM is hard for $\mathsf{DTIME}(n^{2})$ under quasilinear reductions, then $\mathsf{P}\neq\mathsf{NP}$ . Thus, to understand precisely the role of $3$ -SUM to understand quadratic-time computation, the more reasonable question to ask is:

What is the largest class $\mathcal{C}$ of problems such that $3$ -SUM is $\mathcal{C}$ -hard?²²2Note that there are different reasonable notions of reductions to consider. Rather than the quasilinear reductions used by Bloch et al., we will consider the currently more commonly used notion of fine-grained reductions; see Section 1.2 for details on the notion of completeness that we will use.

Finding a large class $\mathcal{C}$ for which $3$ -SUM is hard may be seen as giving evidence for the $3$ -SUM hypothesis. Furthermore, such a result may clarify the true expressive power of the $3$ -SUM hypothesis, much like the NP-completeness of 3-SAT highlights its central role for polynomial intractability.

1.1 Our approach

We approach our central question from a descriptive complexity perspective. This line of research has been initiated by Gao et al. [36], who establish the sparse OV problem as complete for the class of model checking first-order properties. One can interpret this result as showing that the OV problem expresses relational database queries in the sense that a truly subquadratic algorithm for OV would improve the fine-grained data complexity of such queries (see [36] for details). Related works further delineate the fine-grained hardness of model checking first-order properties and related problem classes [49, 14, 12, 7, 13, 32], see Section 1.3 for more discussion.

Towards continuing the line of research on fine-grained completeness theorems, we introduce a class of problems corresponding to deciding formulas in linear integer arithmetic over finite sets of integers. Specifically, consider the vectors

x_{1}=(x_{1}[1],\dots,x_{1}[d_{1}]),\dots,x_{k}=(x_{k}[1],\dots,x_{k}[d_{k}])

as quantified variables, and let $t_{1},\dots,t_{l}$ be free variables. Moreover, let

X:=\{x_{1}[1],\dots,x_{1}[d_{1}],\dots x_{k}[1],\dots,x_{k}[d_{k}],t_{1},\dots% ,t_{l}\},

and let $\psi$ be a quantifier-free linear arithmetic formula over variables in $X$ . We consider the model-checking problem for formulas $\phi$ in the prenex normal form

\phi:=Q_{1}x_{1}\dots Q_{k}x_{k}:\psi,

where the quantifiers $Q_{1},\dots,Q_{k}\in\{\exists,\forall\}$ are arbitrary. Formally, for such a $\phi$ , we define the model checking problem $\mathsf{FOP}_{\mathbb{Z}}(\phi)$ as follows³³3Below, we use the notation $\psi[(t_{1},\dots,t_{l})\backslash(\hat{t_{1}},\dots,\hat{t_{l}})]$ to denote the substitution of the variables $t_{1},\dots,t_{l}$ by $\hat{t_{1}},\dots,\hat{t_{l}}$ respectively.

$\displaystyle\mathsf{FOP}_{\mathbb{Z}}(\phi):$		(1)
Input:	$\displaystyle\text{ Finite sets }A_{1}\subseteq\mathbb{Z}^{d_{1}},\dots,A_{k}% \subseteq\mathbb{Z}^{d_{k}}\text{ and }\hat{t_{1}},\dots,\hat{t_{l}}\in\mathbb% {Z}.$
Problem:	$\displaystyle\text{ Does }Q_{1}x_{1}\in A_{1}\dots Q_{k}x_{k}\in A_{k}:\psi[(t% _{1},\dots,t_{l})\backslash(\hat{t_{1}},\dots,\hat{t_{l}})]\text{ hold?}$

We let $n:=\max_{i}\{|A_{i}|\}$ denote the input size and will assume throughout the paper that all input numbers (i.e., the coordinates of the vectors in $A_{1},\dots,A_{k}$ and the values $\hat{t_{1}},\dots,\hat{t_{l}}$ ) are chosen from a polynomially sized universe, i.e., $\{-U,\dots,U\}$ with $U\leq n^{c}$ for some $c$ . Let $\mathsf{FOP}_{\mathbb{Z}}$ be the union of all $\mathsf{FOP}_{\mathbb{Z}}(\phi)$ problems, where $\phi$ has at least 3 quantifiers.⁴⁴4It is not too difficult to see that all formulas with 2 quantifiers can be model-checked in near-linear time; see the full version for details. Besides $3$ -SUM, a variety of interesting problems is contained in $\mathsf{FOP}_{\mathbb{Z}}$ ; we discuss a few notable examples below and in the full version.

Frequently, we will distinguish formulas in $\mathsf{FOP}_{\mathbb{Z}}$ using their quantifier structure; e.g., $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\forall)$ describes the class of model checking problems $\mathsf{FOP}_{\mathbb{Z}}(\phi)$ where in $\phi$ we have $Q_{1}=Q_{2}=\exists$ and $Q_{3}=\forall.$ Furthermore, we let $\mathsf{FOP}_{\mathbb{Z}}^{k}$ be the union of all $\mathsf{FOP}_{\mathbb{Z}}(\phi)$ problems, where $\phi$ consists of precisely $k$ quantifiers, regardless of their quantifier structure. For a quantifier $Q\in\{\exists,\forall\}$ , we write $Q^{k}$ for the repetition $\underbrace{Q\dots Q}_{k\text{ times}}$ . Finally, we remark that a small subset of $\mathsf{FOP}_{\mathbb{Z}}$ has already been studied by An et al. [7], for a discussion see Section 1.3.

1.2 Our Contributions

We seek to determine completeness results for the class $\mathsf{FOP}_{\mathbb{Z}}$ . In particular: What are the largest fragments of this class for which 3-SUM (or more generally, $k$ -SUM) is complete? Is there a problem that is complete for the entire class?

Intuitively, we say that a $T_{A}(n)$ -time solvable problem $A$ is (fine-grained) complete for a $T_{\mathcal{C}}(n)$ -time solvable class of problems $\mathcal{C}$ , if the existence of an $O(T_{A}(n)^{1-\epsilon})$ -time algorithm for $A$ with $\epsilon>0$ implies that for all problems $C$ in $\mathcal{C}$ there exists $\delta>0$ such that $C$ can be solved in time $O(T_{\mathcal{C}}(n)^{1-\delta})$ . We extend this notion to completeness of a family of problems, since strictly speaking, any (geometric) problem over $\mathbb{Z}^{d}$ expressible in linear integer arithmetic corresponds to a family of formulas $\mathsf{FOP}_{\mathbb{Z}}$ (one for each $d\in\mathbb{N}$ ). Formally, consider a family of problems $\mathcal{P}$ with an associated time bound $T_{\mathcal{P}}(n)$ and a class of problems $\mathcal{C}$ with an associated time bound $T_{\mathcal{C}}(n)$ ; usually $T_{\mathcal{P}}(n),T_{\mathcal{C}}(n)$ denote the running time of the fastest known algorithm solving all problems in $\mathcal{P}$ or $\mathcal{C}$ , respectively (often, we omit these time bounds, as they are clear from context).⁵⁵5Here, we use family and class as a purely semantic and intuitive distinction: A family consists of a small set of similar problems, and a class consists of a large and diverse variety of problems. We say that $\mathcal{P}$ is (fine-grained) complete for $\mathcal{C}$ , if

1.

the family $\mathcal{P}$ is a subset of the class $\mathcal{C}$ , and
2.

if for all problems $P$ in $\mathcal{P}$ there exists $\epsilon>0$ such that $P$ can be solved in time $O(T_{\mathcal{P}}(n)^{1-\epsilon})$ , then for all problems $C$ in $\mathcal{C}$ there exists some $\delta>0$ such that we can solve $C$ in time $O(T_{\mathcal{C}}(n)^{1-\delta})$ .

That is, a polynomial-factor improvement for solving the problems in $\mathcal{P}$ would lead to a polynomial-factor improvement in solving all problems in $\mathcal{C}$ . If a singleton family $\mathcal{P}=\{P\}$ is fine-grained complete for $\mathcal{C}$ , then we also say that $P$ is fine-grained complete for $\mathcal{C}$ . We work with standard hypotheses and problems encountered in fine-grained complexity; for detailed definitions of these, we refer to the full version of this article.

1.2.1 $𝒌$ -SUM is complete for the existential fragment of $\mathsf{FOP}_{\mathbb{Z}}$

Consider first the existential fragment of $\mathsf{FOP}_{\mathbb{Z}}$ , i.e., formulas exhibiting only existential quantifiers. Any $\mathsf{FOP}_{\mathbb{Z}}$ formula with $k$ existential quantifiers can be decided using a standard meet-in-the-middle approach, augmented by orthogonal range search, in time $\tilde{O}(n^{\lceil k/2\rceil})$ ⁶⁶6We use the notation $\tilde{O}(T):=T\log^{O(1)}(T)$ to hide polylogarithmic factors., see the full version of the paper for details. Since $k$ -SUM is a member of $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ , this running time is optimal up to subpolynomial factors, assuming the $k$ -SUM Hypothesis. As our first contribution, we provide a converse reduction. Specifically, we show that a polynomially improved $k$ -SUM algorithm would give a polynomially improved algorithm for solving the entire class. In our language, we show that $k$ -SUM is fine-grained complete for formulas of $\mathsf{FOP}_{\mathbb{Z}}$ with $k$ existential quantifiers.

Theorem 1 ( $k$ -SUM is $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ -complete).

Let $k\geq 3$ and assume that $k$ -SUM can be solved in time $T_{k\mathrm{SUM}}(n)$ . For any problem $P$ in $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ , there exists some $c$ such that $P$ can be solved in time $O(T_{k\mathrm{SUM}}(n)\log^{c}n)$ .

Thus, if there are $k\geq 3$ and $\epsilon>0$ such that we can solve $k$ -SUM in time $O(n^{\lceil k/2\rceil-\epsilon})$ , then we can solve all problems in $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ in time $O(n^{\lceil k/2\rceil-\epsilon^{\prime}})$ for any $0<\epsilon^{\prime}<\epsilon$ . By a simple negation argument, we conclude that $k$ -SUM is also complete for the class of problems $\mathsf{FOP}_{\mathbb{Z}}(\forall^{k})$ .

The above theorem generalizes and unifies previous reductions from problems expressible as $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ formulas to 3-SUM, using different proof ideas: Jafargholi and Viola [39, Lemma 4] give a simple randomized linear-time reduction from triangle detection in sparse graphs to 3-SUM, and a derandomization via certain combinatorial designs. Dudek, Gawrychowski, and Starikovskaya [29] study the family of 3-linear degeneracy testing (3-LDT), which constitutes a large and interesting subset of $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)$ : This family includes, for any $\alpha_{1},\alpha_{2},\alpha_{3},t\in\mathbb{Z}$ , the 3-partite formula $\exists a_{1}\in A_{1}\exists a_{2}\in A_{2}\exists a_{3}\in A_{3}:\alpha_{1}a% _{1}+\alpha_{2}a_{2}+\alpha_{3}a_{3}=t$ and the 1-partite formula $\exists\alpha_{1},\alpha_{2},\alpha_{3}\in A:\alpha_{1}a_{1}+\alpha_{2}a_{2}+% \alpha_{3}a_{3}=t\wedge a_{1}\neq a_{2}\wedge a_{2}\neq a_{3}\wedge a_{1}\neq a% _{3}$ . The authors show that each such formula is either trivial or subquadratic equivalent to $3$ -SUM. For 3-partite formulas, a reduction to $3$ -SUM is essentially straightforward. For 1-partite formulas, Dudek et al. [29] use color coding.⁷⁷7We remark that the reverse direction, i.e., $3$ -SUM-hardness of non-trivial formulas, is technically much more involved and can be regarded as the main technical contribution of [29]. As further examples for reductions from $\mathsf{FOP}_{\mathbb{Z}}$ problems to $k$ -SUM, we highlight a reduction from Vector $k$ -SUM to $k$ -SUM [5] as well as a reduction from $(\min,+)$ -convolution to $3$ -SUM (see [9, 27]) based on a well-known bit-level trick due to Vassilevska Williams and Williams [52], which allows us to reduce inequalities to equalities.

Perhaps surprisingly in light of its generality and applicability, Theorem 1 is obtained via a very simple, deterministic reduction that combines the tricks from [5, 52]. This generality comes at the cost of polylogarithmic factors (which we do not optimize), which depend on the number of inequalities occurring in the considered formula; for the details see Section 3 and the full version of the paper.

1.2.2 Completeness for counting witnesses

We provide a certain extension of the above completeness result to the problem class of counting witnesses to existential $\mathsf{FOP}_{\mathbb{Z}}$ formulas⁸⁸8A witness for a $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ formula $\exists a_{1}\in A_{1}\dots\exists a_{k}\in A_{k}:\varphi$ with $\hat{t_{1}},\dots,\hat{t_{l}}\in\mathbb{Z}$ is a tuple $(a_{1},\dots,a_{k})\in A_{1}\times\cdots\times A_{k}$ that satisfies the formula $\varphi[(t_{1},\dots,t_{l})\backslash(\hat{t_{1}},\dots,\hat{t_{l}})]$ .. Counting witnesses is an important task particularly in database applications (usually referred to as model counting). Furthermore, we will make use of witness counting to decide certain quantified formulas in subsequent results detailed below. In Section 4, we will obtain the following result.

Theorem 2.

Let $k\geq 3$ be odd. If there is $\epsilon>0$ such that we can count the number of witnesses for $k$ -SUM in time $O(n^{\lceil k/2\rceil-\epsilon})$ , then for all problem $P$ in $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ , there is some $\epsilon^{\prime}>0$ such that we can count the number of witnesses for $P$ in time $O(n^{\lceil k/2\rceil-\epsilon^{\prime}})$ .

Leveraging the recent breakthrough by [22] that 3-SUM is subquadratic equivalent to counting witnesses of 3-SUM, we obtain the corollary that 3-SUM is hard even for counting witnesses of $\mathsf{FOP}_{\mathbb{Z}}(\exists^{3})$ .

Corollary 3.

For all problems $P$ in $\mathsf{FOP}_{\mathbb{Z}}(\exists^{3})$ , there is some $\epsilon_{P}>0$ such that we can count the number of witnesses for $P$ in randomized time $O(n^{2-\epsilon_{P}})$ if and only if there is some $\epsilon^{\prime}>0$ such that $3$ -SUM can be solved in randomized time $O(n^{2-\epsilon^{\prime}})$ .

1.2.3 Completeness for general quantifier structures of $\mathsf{FOP}_{\mathbb{Z}}$

In light of our first completeness result, one might wonder whether $k$ -SUM is complete for deciding all $k$ -quantifier formulas in $\mathsf{FOP}_{\mathbb{Z}}$ , regardless of the quantifier structure of the formulas. Note that for these general quantifier structures, a baseline algorithm with running time $\tilde{O}(n^{k-1})$ can be achieved with a combination of brute-force and orthogonal range queries; see the full version for details.

However, by [7, Theorem 15] there exists a $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k-1}\forall)$ -formula $\phi$ that cannot be solved in time $O(n^{k-1-\epsilon})$ -time unless the 3-uniform hyperclique hypothesis is false (see the discussion in Section 1.3). Thus, proving that 3-SUM is complete for all 3-quantifier formulas would establish that the 3-uniform hyperclique hypothesis implies the $3$ -SUM hypothesis – this would be a novel tight reduction among important problems/hypotheses in fine-grained complexity theory. For $k\geq 4$ , it becomes even more intricate: the conditionally optimal running time of $n^{k-1\pm o(1)}$ for $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k}\forall)$ formulas exceeds the conditionally optimal running time of $n^{\lceil\frac{k}{2}\rceil\pm o(1)}$ for $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ formulas.

We are nevertheless able to obtain a completeness result for general quantifier structures: Specifically, we show that if two geometric problems over $\mathbb{Z}^{d}$ can be solved in time $O(n^{2-\epsilon_{d}})$ where $\epsilon_{d}>0$ for all $d$ , then each $k$ -quantifier formula in $\mathsf{FOP}_{\mathbb{Z}}$ can be decided in time $O(n^{k-1-\epsilon})$ for some $\epsilon>0$ . These problems are (1) a variation of the Hausdorff distance that we call Hausdorff distance under $n$ Translations and (2) the Pareto Sum problem; the details are covered in Section 5.

Hausdorff Distance under $𝒏$ Translations

Among the most common translation-invariant distance measures for given point sets $B$ and $C$ is the Hausdorff Distance under Translation [24, 18, 19, 23, 45, 38]. To define it, we denote the directed Hausdorff distance under the $L_{\infty}$ metric by $\delta_{\overrightarrow{H}}(B,C):=\max_{b\in B}\min_{c\in C}\|b-c\|_{\infty}$ .⁹⁹9Since we will exclusively consider the directed Hausdorff distance under Translation, we will drop “directed” throughout the paper. The Hausdorff distance under translation $\delta_{\overrightarrow{H}}^{T}(B,C)$ is defined as the minimum Hausdorff distance of $B$ and an arbitrary translation of $C$ , i.e.,

\delta_{\overrightarrow{H}}^{T}(B,C)\coloneqq\min_{\tau\in\mathbb{R}^{d}}% \delta_{\overrightarrow{H}}(B,C+\{\tau\})=\min_{\tau\in\mathbb{R}^{d}}\max_{b% \in B}\min_{c\in C}\|b-(c+\tau)\|_{\infty}.

For $d=2$ , Bringmann et al. [18] were able to show a $(|B||C|)^{1-o(1)}$ time lower bound based on the orthogonal vector hypothesis, and there exists a matching $\tilde{O}(|B||C|)$ upper bound by Chew et al. [25].

We shall establish that restricting the translation vector to be among a set of $m$ candidate vectors yields a central problem in $\mathsf{FOP}_{\mathbb{Z}}$ . Specifically, we define the Hausdorff distance under Translation in $A$ , denoted as $\delta_{\overrightarrow{H}}^{T(A)}(B,C)$ , by

\delta_{\overrightarrow{H}}^{T(A)}(B,C)\coloneqq\min_{\tau\in A}\delta_{% \overrightarrow{H}}(B,C+\{\tau\})=\min_{\tau\in A}\max_{b\in B}\min_{c\in C}\|% b-(c+\tau)\|_{\infty}.

Correspondingly, we define the problem Hausdorff distance under $m$ Translations as: Given $A,B,C\subseteq\mathbb{Z}^{d}$ with $|A|\leq m$ , $|B|,|C|\leq n$ and a distance value $\gamma\in\mathbb{N}$ , determine whether $\delta_{\overrightarrow{H}}^{T(A)}(B,C)\leq\gamma$ . Note that this can be rewritten as a $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ -formula, see the full version of the paper for details.

The Hausdorff distance under $m$ Translations occurs naturally when approximating the Hausdorff distance under translation: Specifically, common algorithms compute a set $A$ of $|A|=f(\epsilon)$ translations such that $\delta_{\overrightarrow{H}}^{T(A)}(B,C)\leq(1+\epsilon)\delta_{\overrightarrow% {H}}^{T}(B,C)$ . Generally, this problem is then solved by performing $|A|$ computations of the Hausdorff distance, which yields $\tilde{O}(|A|n)=\tilde{O}(f(\epsilon)n)$ -time algorithms [48]. Improving over the $\tilde{O}(mn)$ -time baseline for Hausdorff Distance under $m$ Translations would thus lead to immediate improvements for approximating the Hausdorff Distance under Translation. Our results will establish additional consequences of fast algorithms for this problem: an $O(n^{2-\epsilon_{d}})$ -time algorithm with $\epsilon_{d}>0$ for Hausdorff distance under $n$ Translations would give an algorithmic improvement for the classes of $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ - and $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\forall)$ -formulas.

Verification of Pareto Sums

Our second geometric problem is a verification version of computing Pareto sums: Given point sets $A,B\subseteq\mathbb{Z}^{d}$ , the Pareto sum $C$ of $A, B$ is defined as the Pareto front of their sumset $A+B=\{a+b\mid a\in A,b\in B\}$ . Put differently, the Pareto sum of $A, B$ is a set of points $C$ satisfying (1) $C\subseteq A+B$ , (2) for every $a\in A$ and $b\in B$ , the vector $a+b$ is dominated¹⁰¹⁰10We consider the usual domination notion: A vector $u\in\mathbb{Z}^{d}$ is dominated by some vector $v\in\mathbb{Z}^{d}$ (written $u\leq v$ ) if and only if in all dimensions $i\in[d]$ it holds that $u[i]\leq v[i]$ . by some $c\in C$ and (3) there are no distinct $c,c^{\prime}\in C$ such that $c^{\prime}$ dominates $c$ . The task of computing Pareto sums appears in various multicriteria optimization settings [8, 47, 30, 44]; fast output-sensitive algorithms (both in theory and in practice) have recently been investigated by Hespe, Sanders, Storandt, and Truschel [37].

We consider the following problem as Pareto Sum Verification: Given $A,B,C\subseteq\mathbb{Z}^{d}$ , determine whether

\displaystyle\forall a\in A\forall b\in B\exists c\in C:a+b\leq c.

The complexity of Pareto Sum Verification¹¹¹¹11We remark that our problem definition only checks a single of the three given conditions, specifically, condition (2). However, in Section 7, we will establish that the verifying all three conditions reduces to verifying this single condition. More specifically, for sets $A, B, C$ of size at most $n$ , we obtain that if we can solve Pareto Sum Verification in time $T(n)$ , then we can check whether $C$ is the Pareto sum of $A, B$ in time $O(T(n))$ . is tightly connected to output-sensitive algorithms for Pareto Sum. Specifically, solving Pareto Sum Verification reduces to computing the Pareto sum $C$ when given inputs $A, B$ of size at most $n$ with the promise that $|C|=\Theta(n)$ ; see Section 7 for details. The work of Hespe et al. [37] gives a practically fast $O(n^{2})$ -time algorithm in this case for $d=2$ ; note that for $d\geq 3$ , we still obtain an $\tilde{O}(n^{2})$ -time algorithm via our Baseline Algorithm, which is described in the full version of the paper.

A problem pair that is complete for $\mathsf{FOP}_{\mathbb{Z}}$

As a pair, these two geometric problems turn out to be fine-grained complete for the class $\mathsf{FOP}_{\mathbb{Z}}$ .

Theorem 4.

There is a function $\epsilon(d)>0$ such that both of the following problems can be solved in time $O(n^{2-\epsilon(d)})$

$\blacksquare$

Pareto Sum Verification,
$\blacksquare$

Hausdorff distance under $n$ Translations,

if and only if for each problem $P$ in $\mathsf{FOP}_{\mathbb{Z}}^{k}$ with $k\geq 3$ there exists an $\epsilon_{P}>0$ such that $P$ can be solved in time $O(n^{k-1-\epsilon_{P}})$ .

The above theorem shows that a single pair of natural problems captures the fine-grained complexity of the expressive and diverse class $\mathsf{FOP}_{\mathbb{Z}}$ . As an illustration just how expressive this class is, we observe the following barriers:¹²¹²12The first three statements follow from $\mathsf{FOP}_{\mathbb{Z}}$ generalizing the class $P T O$ studied in [7], see Section 1.3. The remaining statements rely on the additive structure of $\mathsf{FOP}_{\mathbb{Z}}$ .

1.

If there is some $\epsilon>0$ such that all problems in $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\forall)$ (or $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ ) can be solved in time $O(n^{2-\epsilon})$ , then OVH (and thus SETH) is false [7, Theorem 16].
2.

If there is some $\epsilon>0$ such that all problems in $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ (or $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\forall)$ ) can be solved in time $O(n^{2-\epsilon})$ , then the Hitting Set Hypothesis is false [7, Theorem 12].
3.

If for all problems $P$ in $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\forall)$ (or $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ ), there exists some $\epsilon>0$ such that we can solve $P$ in $O(n^{2-\epsilon})$ , then the 3-uniform Hyperclique Hypothesis is false [7, Theorem 15].
4.

If for all problems $P$ in $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)$ ( $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\forall),\mathsf{FOP}_{\mathbb{Z}}(% \forall\forall\exists)$ , or $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\forall)$ ), there exists some $\epsilon>0$ such that we can solve $P$ in time $O(n^{2-\epsilon})$ , then the $3$ -SUM Hypothesis is false (Theorem 1 with Lemma 11).

Theorem 4 raises the question whether for any constant dimension $d$ , the Hausdorff distance under $n$ Translations admits a subquadratic reduction to Pareto Sum Verification. A positive answer would establish Pareto Sum Verification as complete for the entire class $\mathsf{FOP}_{\mathbb{Z}}$ . We elaborate on this in Section 8.

1.2.4 $3$ -SUM is complete for $\mathsf{FOP}_{\mathbb{Z}}$ formulas of low inequality dimension

Returning to our motivating question, we ask: Since it appears unlikely to prove completeness of 3-SUM for all $\mathsf{FOP}_{\mathbb{Z}}$ formulas (as this requires a tight 3-uniform hyperclique lower bound for 3-SUM), can we at least identify a large fragment of $\mathsf{FOP}_{\mathbb{Z}}$ for which $3$ -SUM is complete? In particular, can we extend our first result of Theorem 1 from existentially quantified formulas to substantially different problems in $\mathsf{FOP}_{\mathbb{Z}}$ , displaying other quantifier structures?

Surprisingly, we are able to show that $3$ -SUM is complete for low-dimensional $\mathsf{FOP}_{\mathbb{Z}}$ formulas, independent of their quantifier structure. To formalize this, we introduce the inequality dimension of a $\mathsf{FOP}_{\mathbb{Z}}$ formula as the smallest number of linear inequalities required to model it. More formally, consider a $\mathsf{FOP}_{\mathbb{Z}}$ formula $\phi=Q_{1}x_{1}\in A_{1},\dots,Q_{k}x_{k}\in A_{k}:\psi$ with $A_{i}\subseteq\mathbb{Z}^{d_{i}}$ . The inequality dimension of $\phi$ is the smallest number $s$ such that there exists a Boolean function $\psi^{\prime}:\{0,1\}^{s}\to\{0,1\}$ and (strict or non-strict) linear inequalities $L_{1},\dots,L_{s}$ in the variables $\{x_{i}[j]:i\in\{1,\dots,k\},j\in\{1,\dots,d_{i}\}\}$ and the free variables such that $\psi(x_{1},\dots,x_{k})$ is equivalent to $\psi^{\prime}(L_{1},\dots,L_{s})$ . As an example, the 3-SUM formula $\exists a\in A\exists b\in B\exists c\in C:a+b=c$ has inequality dimension 2, as $a+b=c$ can be modelled as conjunction of the two linear inequalities $a+b\leq c$ and $a+b\geq c$ , whereas no single linear inequality can model $a+b=c$ .

We show that $3$ -SUM is fine-grained complete for model-checking $\mathsf{FOP}^{3}_{\mathbb{Z}}$ formulas with inequality dimension at most $3$ . This result is our perhaps most interesting technical contribution and intuitively combines our result that $3$ -SUM is hard for counting $\mathsf{FOP}_{\mathbb{Z}}$ witnesses (Corollary 3) with a geometric argument, specifically, that the union of $n$ unit cubes in $\mathbb{R}^{3}$ can be decomposed into the union of $O(n)$ pairwise interior- and exterior-disjoint axis-parallel boxes. To this end, we extend a result from [23], which constructs pairwise interior-disjoint axis-parallel boxes, to also achieve exterior-disjointness. For more details, see the Technical Overview below and Section 6.

Theorem 5.

There is an algorithm deciding $3$ -SUM in randomized time $O(n^{2-\epsilon})$ for an $\epsilon>0$ , if and only if for each problem $P$ in $\mathsf{FOP}^{k}_{\mathbb{Z}}$ with $k\geq 3$ and inequality dimension at most $3$ , there exists some $\epsilon>0$ such that we can solve $P$ in randomized time $O(n^{k-1-\epsilon})$ .

Note that this fragment of $\mathsf{FOP}_{\mathbb{Z}}$ contains a variety of interesting problems. A general example is given by comparisons of sets defined using the sumset arithmetic¹³¹³13The sumset arithmetic uses the sumset operator $X+Y$ to denote the sumset $\{x+y\mid x\in X,y\in Y\}$ and $\lambda X$ to denote $\{\lambda x\mid x\in X\}$ ., which correspond to formulas of inequality dimension at most 2: E.g., checking, given sets $A,B,C\subseteq\mathbb{Z}$ and $t\in\mathbb{Z}$ , whether $C$ is an additive $t$ -approximation of the sumset $A+B$ is equivalent to verifying the conjunction of the $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ problem¹⁴¹⁴14Note that the corresponding formula is $\forall a\in A\forall b\in B\exists c\in C:(c\leq a+b)\wedge(a+b\leq c+t)$ , which clearly has inequality dimension at most 2. $A+B\subseteq C+\{0,\dots,t\}$ and (2) the $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)$ problem¹⁵¹⁵15Note that the corresponding formula is $\forall c\in C\exists a\in A\exists b\in B:a+b=c$ , which clearly has inequality dimension at most 2. $C\subseteq A+B$ . Likewise, this extends to $\lambda$ -multiplicative approximations of sumsets. Furthermore, the problems corresponding to general sumset comparisons like $\alpha_{1}A_{1}+\cdots+\alpha_{i}A_{i}\subseteq\alpha_{i+1}A_{i+1}+\cdots+% \alpha_{k}A_{k}+\{-\ell,\dots,u\}$ have inequality dimension at most $2$ as well.

Our results of Theorems 4 and 5 suggests to view Pareto Sum Verification as a geometric, high-dimensional generalization of $3$ -SUM. Furthermore, it remains an interesting problem to establish the highest $d$ such that 3-SUM is complete for $\mathsf{FOP}_{\mathbb{Z}}$ formulas of inequality dimension at most $d$ ; for a discussion see Section 8.

Further Applications

As an immediate application of our first completeness theorem, we obtain a simple proof of a $n^{4/3-o(1)}$ lower bound for the 4-SUM problem based on the the $3$ -uniform hyperclique hypothesis; see the full version of the paper for details. Specifically, by Theorem 1, it suffices to model the 3-uniform 4-hyperclique problem as a problem in $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists\exists)$ . The resulting conditional lower bound is implicitly known in the literature, as it can alternatively be obtained by combining a 3-uniform hyperclique lower bound for $4$ -cycle given in [43] with a folklore reduction from $4$ -cycle to $4$ -SUM (see [39] for a deterministic reduction from $3$ -cycle to $3$ -SUM).

Theorem 6.

If there is some $\epsilon>0$ such that 4-SUM can be solved in time $O(n^{\frac{4}{3}-\epsilon})$ , then the 3-uniform hyperclique hypothesis fails.

Similarly, we can also give a simple proof for a known lower bound for $3$ -SUM.

Another application of our results is to establish class-based conditional bounds. As a case in point, consider the problem of computing the Pareto sum of $A,B\subseteq\mathbb{Z}^{d}$ : Clearly, this problem can be solved in time $\tilde{O}(n^{2})$ by explicitly computing the sumset $A+B$ and computing the Pareto front using any algorithm running in near-linear time in its input, e.g. [34]. We prove the following conditional optimality results already in the case when the desired output (the Pareto sum of $A, B$ ) has size $\Theta(n)$ .

Theorem 7 (Pareto Sum Computation Lower Bound).

The following conditional lower bounds hold for output-sensitive Pareto sum computation:

1.

If there is $\epsilon>0$ such that we can compute the Pareto sum $C$ of $A,B\subseteq\mathbb{Z}^{2}$ , whenever $C$ is of size $\Theta(n)$ , in time $O(n^{2-\epsilon})$ , then the $3$ -SUM hypothesis fails (thus, for any $\mathsf{FOP}_{\mathbb{Z}}^{k}$ formula $\phi$ of inequality dimension at most 3, there is $\epsilon^{\prime}>0$ such that $\phi$ can be decided in time $O(n^{k-1-\epsilon^{\prime}})$ ).
2.

If for all $d\geq 2$ , there is $\epsilon>0$ such that we can compute the Pareto sum $C$ of $A,B\subseteq\mathbb{Z}^{d}$ , whenever $C$ is of size $\Theta(n)$ , in time $O(n^{2-\epsilon})$ , then there is some $\epsilon^{\prime}>0$ such that we can decide all $\mathsf{FOP}_{\mathbb{Z}}$ formulas with $k$ quantifiers not ending in $\exists\forall\exists$ or $\forall\exists\forall$ in time $O(n^{k-1-\epsilon^{\prime}})$ .

Our lower bound for 2D strengthens a quadratic-time lower bound found by Funke et al. [33] based on the $(\min,+)$ -convolution hypothesis to hold already under the weaker (i.e., more believable) $3$ -SUM hypothesis. For higher dimensions, we furthermore strengthen the conditional lower bound via its connection to $\mathsf{FOP}_{\mathbb{Z}}$ .

We conclude with remaining open questions in Section 8.

1.3 Further Related Work

To our knowledge, the first investigation of the connection between classes of model-checking problems and central problems in fine-grained complexity was given by Williams [49], who shows that the $k$ -clique problem is complete for the class of existentially-quantified first order graph properties, among other results. As important follow-up work, Gao et al. [36] establish OV as complete problem for model-checking any first-order property.

Subsequent results include classification results for $\exists^{k}\forall$ -quantified first-order graph properties [14], fine-grained upper and lower bounds for counting witnesses of first-order properties [28], completeness theorems for multidimensional ordering properties [7] (discussed below), completeness and classification results for optimization classes [12, 13] as well as an investigation of sparsity for monochromatic graph properties [32].

We remark that An et al. [7] study completeness results for a strict subset of $\mathsf{FOP}_{\mathbb{Z}}$ formulas: Specifically, they introduce a class $\mathsf{PTO}_{k,d}$ of $k$ -quantifier first-order sentences over inputs $\mathbb{N}^{d}$ (or, without loss of generality $\{1,\dots,n\}^{d}$ ) that may only use comparisons of coordinates (and constants). Note that such sentences lack additive structure, and indeed the fine-grained complexity differs decisively from $\mathsf{FOP}_{\mathbb{Z}}$ : E.g., for $\mathsf{PTO}(\exists\exists\exists)$ formulas, they establish the sparse triangle detection problem as complete, establishing a conditionally tight running time of $m^{2\omega/(\omega+1)\pm o(1)}$ . This is in stark contrast to $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)$ formulas, for which we establish $3$ -SUM as complete problem, yielding a conditionally optimal running time of $n^{2\pm o(1)}$ . In particular, for each 3-quantifier structure $Q_{1}Q_{2}Q_{3}$ , a $O(n^{2-\epsilon})$ -time algorithm for all $\mathsf{FOP}_{\mathbb{Z}}(Q_{1}Q_{2}Q_{3})$ problems would break a corresponding hardness barrier¹⁶¹⁶16Specifically, an $O(n^{2-\epsilon})$ time algorithm for problems in $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists),\mathsf{FOP}_{\mathbb{Z}}(% \forall\forall\forall),\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ , or $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\forall)$ with $\epsilon>0$ would refute the $3$ -SUM hypothesis. Furthermore, an $O(n^{2-\epsilon})$ time algorithm for problems in $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)$ , $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\forall)$ , $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ , or $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\forall)$ with $\epsilon>0$ would immediately yield an improvement for the MaxConv lower bound problem [27]; for details see the full version of the paper..

Since any $\mathsf{PTO}_{k,d}$ formula is also a $\mathsf{FOP}_{\mathbb{Z}}$ formula with the same quantifier structure, any hardness result in [7] for $\mathsf{PTO}(Q_{1},\dots,Q_{k})$ carries over to $\mathsf{FOP}_{\mathbb{Z}}(Q_{1},\dots,Q_{k})$ . On the other hand, any of our algorithmic results for $\mathsf{FOP}_{\mathbb{Z}}(Q_{1},\dots,Q_{k})$ transfers to its subclass $\mathsf{PTO}(Q_{1},\dots,Q_{k})$ .

2 Technical Overview

In this section, we sketch the main ideas behind our proofs.

Completeness of $𝒌$ -SUM for $\mathsf{FOP_{\mathbb{Z}}}(\exists^{k})$

With the right ingredients, proving that $k$ -SUM is complete for $\mathsf{FOP}_{\mathbb{Z}}$ formulas with $k$ existential quantifiers (Theorem 1) is possible via a simple approach: We observe that any $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ formula $\phi$ can be rewritten such that we may assume that $\phi$ is a conjunction of $m$ inequalities. We then use a slight generalization of a bit-level trick of [52] to reduce each inequality to an equality, incurring only $O(\log n)$ overhead per inequality (intuitively, we need to guess the most significant bit position at which the left-hand side and the right-hand side differ). Thus, we obtain $O(\log^{m}n)$ conjunctions of $m$ equalities; each such conjunction can be regarded as an instance of Vector $k$ -SUM. Using a straightforward approach for reducing Vector $k$ -SUM to $k$ -SUM given in [5], the reduction to $k$ -SUM follows. We give all details in Section 3 and the full version of the paper.

Counting witnesses and handling multisets

While the reduction underlying Theorem 1 preserves the existence of solutions, it fails to preserve the number of solutions. The challenge is that when applying the bit-level trick to reduce inequalities to equalities, we need to make sure that for each witness of a $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ formula $\phi$ , there is a unique witness in the $k$ -SUM instances produced by the reduction. While it is straightforward to ensure that we do not produce multiple witnesses, the subtle issue arises that distinct witnesses for $\phi$ may be mapped to the same witness in the $k$ -SUM instances. It turns out that it suffices to solve a multiset version of # $k$ -SUM, i.e., to count all witnesses in a $k$ -SUM instance in which each input number may occur multiple times.

Thus, to obtain Theorem 2, we show a fine-grained equivalence of Multiset # $k$ -SUM and # $k$ -SUM, for all odd $k\geq 3$ . This fine-grained equivalence, which we prove via a heavy-light approach, might be of independent interest.¹⁷¹⁷17We remark that it is plausible that the proof of the subquadratic equivalence of $3$ -SUM and # $3$ -SUM due to Chan et al. [22] could be extended to establish subquadratic equivalence with Multiset # $3$ -SUM as well. Note, however, that a fine-grained equivalence of # $k$ -SUM and $k$ -SUM is not known for any $k\geq 4$ . Combining this equivalence with an inclusion-exclusion argument, we may thus lift Theorem 1 to a counting version for all odd $k\geq 3$ .

In the reductions below, we will make crucial use of the immediate corollary of Theorem 2 and [22] that for each $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)$ formula $\phi$ , there exists a subquadratic reduction from counting witnesses for $\phi$ to $3$ -SUM (Corollary 3).

On general quantifier structures

We perform a systematic study on the different quantifier structures for $k=3$ . Due to simple negation arguments, we only have to perform a systematic study on the classes of problems $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)$ , $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)$ , $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ , $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ .

First, we state a simple lemma establishing syntactic complete problems for the classes above.

Lemma 8 (Syntactic Complete problems (Informal Version)).

Let $Q_{1},Q_{2}\in\{\exists,\forall\}$ . We can reduce every formula of the class $\mathsf{FOP}_{\mathbb{Z}}(Q_{1}Q_{2}\exists)$ to the formula

Q_{1}\tilde{a_{1}}\in\tilde{A_{1}}Q_{2}\tilde{a_{2}}\in\tilde{A_{2}}\exists% \tilde{a_{3}}\in\tilde{A_{3}}:\tilde{a_{1}}+\tilde{a_{2}}\leq\tilde{a_{3}}.

On the quantifier change $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)\to\mathsf{FOP}_{\mathbb{Z}}(% \exists\exists\exists)$

We rely on the subquadratic equivalence between $3$ -SUM and a functional version of $3$ -SUM called All-ints $3$ -SUM, which asks to determine for every $a\in A$ whether there is a solution involving $a$ . A randomized subquadratic equivalence was given in [51], which can be turned deterministic [42].

This equivalence allows us to use the bit-level trick to turn inequalities to equalities, despite it seemingly not interacting well with the quantifier structure $\forall\exists\exists$ at first sight. This results in a proof of the following hardness result.

Lemma 9.

If $3$ -SUM can be solved in time $O(n^{2-\epsilon})$ for an $\epsilon>0$ , then all problems $P$ of $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)$ can be solved in time $O(n^{2-\epsilon_{P}})$ for an $\epsilon_{P}>0$ .

On the quantifier change $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)\to\mathsf{FOP}_{\mathbb{Z}}(% \forall\forall\exists)$

As a first result for the class $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ , we are able to show equivalence to $3$ -SUM for a specific problem in this class, thus introducing a $3$ -SUM equivalent problem with a different quantifier structure in comparison to $3$ -SUM. Specifically, we consider the problem of verifying additive $t$ -approximation of sumsets. We are able to precisely characterize the fine-grained complexity depending on $t$ .

Formally, we show the following theorem.

Theorem 10.

Consider the Additive Sumset Approximation problem of deciding, given $A,B,C\subseteq\mathbb{Z},t\in\mathbb{Z}$ , whether

A+B\subseteq C+\{0,\dots,t\}.

This problem is

$\blacksquare$

solvable in time $O(n^{2-\delta})$ with $\delta>0$ , whenever $t=O(n^{1-\epsilon})$ for any $\epsilon>0,$
$\blacksquare$

not solvable in time $O(n^{2-\epsilon})$ , whenever $t=\Omega(n)$ assuming the Strong $3$ -SUM hypothesis.

Furthermore, subquadratic hardness holds under the standard 3-SUM Hypothesis if no restriction on $t$ is made.

The above theorem is essentially enabling a quantifier change transforming the $\exists\exists\exists$ quantifier structure for which $3$ -SUM is complete into a subquadratic equivalent problem with a quantifier structure $\forall\forall\exists$ . Moreover, the $3$ -SUM hardness is a witness to the hardness of the class $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ .

Let us remark a few interesting aspects: The algorithmic part follows from sparse convolution techniques going back to Cole and Hariharan [26], see [16] for a recent account and also [20, 17, 15]. Specifically, whenever $t=O(n^{1-\epsilon})$ , it holds that $|C+\{0,\dots,t\}|=O(n^{2-\epsilon})$ and intuitively, we can use an output-sensitive convolution algorithm to compute $A+B$ and compare it to $C+\{0,\dots,t\}$ .¹⁸¹⁸18The argument is slightly more subtle, since we need to avoid computing $A+B$ if its size exceeds $O(n^{2-\epsilon})$ . Our result indicates that an explicit construction of $C+\{0,\dots,t\}$ is required, since once it may get as large as $\Omega(n^{2})$ , we obtain a $n^{2-o(1)}$ -time lower bound assuming the Strong $3$ -SUM Hypothesis.

The lower bound follows from describing the $3$ -SUM problem alternatively as $(A+B)\cap C\neq\emptyset$ , which is equivalent to the negation of $(A+B)\subseteq\bar{C}$ , where $\bar{C}$ denotes the complement of $C$ . Thus, we aim to cover the complement of $C$ by intervals of length $t$ . While this appears impossible for $3$ -SUM, we employ the subquadratic equivalence of $3$ -SUM and its convolutional version due to Patrascu [46]. This problem will deliver us the necessary structure to represent this complement with the addition of few auxilliary points.

The reverse reduction from Additive Sumset Approximation to $3$ -SUM follows from Theorem 5 (as Additive Sumset Approximation has inequality dimension $2$ ).

On completeness results for $\mathsf{FOP}_{\mathbb{Z}}^{k}$

The above ingredients establish our completeness theorems by exhaustive search over remaining quantifiers. Specifically, by a combination of Theorem 10, which shows that Additive Sumset Approximation is $3$ -SUM hard, and a combination of Lemma 9 and Theorem 1, we get:

Lemma 11.

There is a function $\epsilon(d)>0$ such that the Verification of Pareto Sum problem can be solved in time $O(n^{2-\epsilon(d)})$ if and only if all problems $P$ in the classes

$\blacksquare$

$\mathsf{FOP}_{\mathbb{Z}}(Q_{1}\dots Q_{k-3}\exists\exists\exists)$ , $\mathsf{FOP}_{\mathbb{Z}}(Q_{1}\dots Q_{k-3}\forall\forall\forall),$
$\blacksquare$

$\mathsf{FOP}_{\mathbb{Z}}(Q_{1}\dots Q_{k-3}\forall\exists\exists)$ , $\mathsf{FOP}_{\mathbb{Z}}(Q_{1}\dots Q_{k-3}\exists\forall\forall),$
$\blacksquare$

$\mathsf{FOP}_{\mathbb{Z}}(Q_{1}\dots Q_{k-3}\forall\forall\exists)$ , $\mathsf{FOP}_{\mathbb{Z}}(Q_{1}\dots Q_{k-3}\exists\exists\forall),$

where $Q_{1},\dots Q_{k-3}\in\{\exists,\forall\}$ and $k\geq 3$ , can be solved in time $O(n^{k-1-\epsilon_{P}})$ for an $\epsilon_{P}>0$ .

Similarly, for quantifier structures ending in $\exists\forall\exists$ and $\forall\exists\forall$ , we obtain the following completeness result.

Lemma 12.

There is a function $\epsilon(d)>0$ such that the Hausdorff Distance under $n$ Translations problem can be solved in time $O(n^{2-\epsilon(d)})$ if and only if all problems $P$ in the classes

$\blacksquare$

$\mathsf{FOP}_{\mathbb{Z}}(Q_{1}\dots Q_{k-3}\exists\forall\exists),\mathsf{FOP% }_{\mathbb{Z}}(Q_{1}\dots Q_{k-3}\forall\exists\forall),$

where $Q_{1},\dots Q_{k-3}\in\{\exists,\forall\}$ and $k\geq 3$ , can be solved in time $O(n^{k-1-\epsilon_{P}})$ for an $\epsilon_{P}>0$ .

The combination of Lemma 11 and Lemma 12, thus suffice to prove Theorem 4.

The $3$ -SUM completeness of formulas with inequality dimension at most $3$

As a first idea, one could try to solve problems of different quantifier structures by just counting witnesses. Consider in the following the example $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ .

Assume we are promised that the formula $\forall a\in A\forall b\in B\exists c\in C\psi(a,b,c)$ satisfies a kind of disjointness property, specifically that for every $(a,b)\in A\times B$ there exists at most one $c\in C$ such that $\psi(a,b,c)$ . Then satisfying the formula boils down to checking whether the number of witnesses $(a,b,c)$ satisfiying $\psi(a,b,c)$ equals to $|A|\cdot|B|$ .

To create this disjointness effect, we use the following geometric approach: We show that one can re-interpret the formula as $\forall a\in A\forall b\in B:a+b\in\bigcup_{c^{\prime}\in C^{\prime}}V(c^{% \prime})$ , where $A,B,C^{\prime}\subseteq\mathbb{Z}^{3}$ , $C^{\prime}$ is a set of size $O(n)$ and $V(c^{\prime})$ is an orthant associated to $c^{\prime}$ . Using an adapted variant of [23], we decompose this union of orthants in $\mathbb{R}^{3}$ (which we may equivalently view as sufficiently large congruent cubes) into a set $\mathcal{R}$ of $O(n)$ disjoint boxes. Thus, it remains to notice that the resulting problem – i.e., for all $a\in A,b\in B$ is there a box $R\in\mathcal{R}$ such that $a+b$ is contained in $R$ – is a $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ formula with the desired disjointness property, which can be handled as argued above.

For the class $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ , we perform a slightly more involved argument. The classes $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)$ and $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)$ reduce to $3$ -SUM regardless of the inequality dimension due to Theorem 1 and Lemma 9.

3 $𝒌$ -SUM is complete for existential $\mathsf{FOP}_{\mathbb{Z}}$ formulas

We begin with a simple completeness theorem that $k$ -SUM is complete for the class of problems $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ . Since $k$ -SUM is indeed a $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ -formula, it remains to show a fine-grained reduction from any $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ formula to $k$ -SUM. The proofs in this section are deferred to the full version. As a first step towards this Theorem, we consider how to reduce a conjunction of $m$ linear inequalities to a vector $k$ -SUM instance.

Lemma 13.

Consider vectors $a_{1}\in\{-U,\dots,U\}^{d_{1}},\dots,a_{k}\in\{-U,\dots,U\}^{d_{k}},$ integers $S_{1},\dots,S_{m}\in\{-U,\dots,U\},$ for each $i\in\{1,\dots,m\},j\in\{1,\dots,k\}$ , vectors $c_{i,j}\in\mathbb{Z}^{d_{j}}$ , and a formula

\psi:=\bigwedge_{i=1}^{m}\left(\sum_{j=1}^{k}c_{i,j}^{T}a_{j}\geq S_{i}\right).

There exist $O(1)$ time computable functions $f_{1}^{\ell,\psi},\dots,f_{k}^{\ell,\psi},g^{\ell,\psi,W}$ such that the following statements are equivalent

1.

The formula $\bigwedge_{i=1}^{m}\left(\sum_{j=1}^{k}c_{i,j}^{T}a_{j}\geq S_{i}\right)$ holds.
2.

There are $\ell\in\{1,\dots,\lceil\log_{2}(M)\rceil\}^{m},W\in\{1,\dots,k\}^{m}$ such that $f^{\ell,\psi}_{1}(a_{1})+\dots+f^{\ell,\psi}_{k}(a_{k})=g^{\ell,\psi,W}(S_{1},% \dots,S_{m}).$

Moreover, if the second item holds, there is a unique choice of such $\ell$ and $W$ .

Essentially the above lemma enables a reduction from a conjunction of inequality checks to a conjunction of equality checks. We can now continue with our completeness theorem. See 1 Ater applying Lemma 13, it remains to reduce a conjunction of equality checks to $k$ -SUM. To do so, we interpret the conjunction of equalities as a Vector $k$ -SUM problem, which can be reduced to $k$ -SUM in a straightforward way [5].

4 On counting witnesses in $\mathsf{FOP}_{\mathbb{Z}}$

In this section, we show reductions from counting witnesses of $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ formulas to $\#k$ -SUM, specifically, we prove Theorem 2. To do so, we adapt the proof of Theorem 1 given in Section 3 to a counting version. As discussed in Section 2, this requires us to work with a multiset version of # $k$ -SUM. Handling multisets is thus the main challenge addressed in this section. Formally, we say that a multiset is a set $A$ together with a function $f:A\to\mathbb{N}$ . For $a\in A$ , we abbreviate $n_{a}:=f(a)$ as the multiplicity of $a$ . To measure multiset sizes, we still think of each $a$ to have $n_{a}$ copies in the input, i.e. the size of $A$ is $\sum_{a\in A}n_{a}$ . Almost all proofs in this section are deferred to the full version of the paper.

Definition 14 ( $(U,d)$ -vector Multiset $\#k$ -SUM).

Let $X:=\{-U,\dots,U\}^{d}$ . Given $k$ multisets $A_{1},\dots,A_{k}\subseteq X$ and $t\in X$ , we ask for the total number of $k$ -SUM witnesses, that is

\displaystyle\sum_{\begin{subarray}{c}a_{1}+\dots+a_{k}=t,\\ a_{1}\in A_{1},\dots,a_{k}\in A_{k}\end{subarray}}\prod_{i=1}^{k}n_{a_{i}}.

Furthermore, define Multiset $\#k$ -SUM as $(U,1)$ -vector Multiset $\#k$ -SUM and $M$ -multiplicity $\#k$ -SUM as Multiset $\#k$ -SUM with the additional restriction that the multiplicity of each element is limited, that is for all $a\in A_{1}\cup\dots\cup A_{k}:n_{a}\leq M$ holds. Lastly, $\#k$ -SUM is defined as $1$ -Multiplicity $\#k$ -SUM and $(U,d)$ -vector $\#k$ -SUM is $(U,d)$ -vector Multiset $\#k$ -SUM where for all $a\in A_{1}\cup\dots\cup A_{k}:n_{a}=1$ holds.

For the case of $\mathsf{FOP}_{\mathbb{Z}}^{3}$ we will also introduce the $\#$ All-ints version of the above problems, which asks to determine, for each $a_{1}\in A_{1}$ , the number of witnesses involving $a_{1}$ .

The (deferred) proof of the following lemma is analogous to the proof of Abboud et al. [5] to reduce Vector $k$ -SUM to $k$ -SUM.

Lemma 15 ( $(U,d)$ -vector Multiset $\#k$ -SUM $\leq_{\lceil k/2\rceil}$ Multiset $\#k$ -SUM).

If Multiset $\#k$ -SUM can be solved in time $T(n)$ then $(U,d)$ -vector Multiset $\#k$ -SUM can be solved in time $O(nd\log(U)+T(n)).$

Next, we give a simple approach to solve Multiset $\#k$ -SUM when all multiplicities are comparably small.

Lemma 16 ( $M$ -multiplicity $\#k$ -SUM $\leq_{\lceil k/2\rceil}$ $\#k$ -SUM).

If $\#k$ -SUM can be solved in time $T(n)$ , then $M$ -multiplicity $\#k$ -SUM can be solved in time $\tilde{O}(T(nM^{k-1}))$ .

For later purposes, we will need the following version of the above lemma.

Observation 17.

If $\#$ All-ints $3$ -SUM can be solved in time $T(n)$ , then we can solve $\#$ All-ints $M$ -multiplicity $3$ -SUM in time $\tilde{O}(T(nM^{2})).$

We can finally prove the main result of this section.

Lemma 18.

For odd $k\geq 3$ , if there exists an algorithm for the $\#k$ -SUM problem running in time $O(n^{\lceil k/2\rceil-\epsilon})$ for an $\epsilon>0$ , then there exists an algorithm for the Multiset $\#$ k-SUM problem running in time $O(n^{\lceil k/2\rceil-\epsilon^{\prime}})$ for an $\epsilon^{\prime}>0$ .

Proof.

We proceed with a heavy-light approach. Assume there exists an $O(n^{\lceil k/2\rceil-\epsilon})$ algorithm for the $\#k$ -SUM problem. Set $c:=(k-1)(\lceil k/2\rceil)$ . Firstly, we count the number of solutions $(a_{1},\dots,a_{k})\in A_{1}\times\dots\times A_{k}$ , where $n_{a_{1}},\dots,n_{a_{k}}\leq n^{\epsilon/c}$ using Lemma 16. This takes time

	$\displaystyle\tilde{O}\left((n\cdot(n^{\epsilon/c})^{k-1})^{\lceil k/2\rceil-% \epsilon}\right)$	$\displaystyle=\tilde{O}\left(\left(n^{1+\frac{\epsilon}{\lceil k/2\rceil}}% \right)^{\lceil k/2\rceil-\epsilon}\right)$
		$\displaystyle=\tilde{O}\left(n^{{\lceil k/2\rceil-\epsilon}+\epsilon-\frac{% \epsilon^{2}}{\lceil k/2\rceil}}\right)$
		$\displaystyle=O\left(n^{\lceil k/2\rceil-\epsilon^{\prime}}\right),$

where $\epsilon^{\prime}>0$ . It remains to calculate the number of witnesses $(a_{1},\dots,a_{k})$ , where for at least one $i\in\{1,\dots,k\}$ , we have high multiplicity, meaning $n_{a_{i}}>n^{\epsilon/c}$ holds. Consider the case that $a_{1}\in A_{1}$ is a high-multiplicity number (the case where $a_{i}\in A_{i}$ with $i\neq 1$ is a high-multiplicity number is analogous). For each high-multiplicity number $a_{1}$ in $A_{1}$ we do the following. Solve the $(k-1)$ -SUM instance with sets $A_{2},\dots,A_{k}$ and target $t-a_{1}$ . There are at most $n^{1-(\epsilon/c)}$ many high-multiplicity numbers in $A_{1}$ , and solving the $(k-1)$ -SUM instance takes time $O(n^{(k-1)/2})$ , since $k$ is odd. We get a total runtime of

	$\displaystyle n^{1-\frac{\epsilon}{c}}\cdot\tilde{O}(n^{(k-1)/2})$	$\displaystyle=\tilde{O}(n^{1-(\epsilon/c)+(k-1)/2})$
		$\displaystyle=\tilde{O}(n^{(k+1)/2-(\epsilon/c)})$
		$\displaystyle=O(n^{\lceil k/2\rceil-\epsilon^{\prime\prime}}),$

where $\epsilon^{\prime\prime}>0$ , which concludes the proof. $\hfill\blacktriangleleft$

See 2

By combining the subquadratic equivalence between $3$ -SUM and $\#3$ -SUM due to Chan et al. [22] and the above theorem, we obtain the following corollary. See 3

The above proof can also be adapted for the special case $k=3$ to count for each $a_{1}\in A_{1}$ the number of witnesses involving $a_{1}$ , by plugging in the appropriate All-ints versions; see the full version of the paper for details. Together with the equivalence between $\#$ All-ints $3$ -SUM and $3$ -SUM of Chan et al. [22], we get

Corollary 19.

For all problems $P$ in $\mathsf{FOP}_{\mathbb{Z}}(\exists^{3})$ , we are able to count for each $a_{1}\in A_{1}$ the number of witnesses involving $a_{1}$ in randomized time $O(n^{2-\epsilon})$ for an $\epsilon>0$ , if $3$ -SUM can be solved in randomized time $O(n^{2-\epsilon^{\prime}})$ for an $\epsilon^{\prime}>0$ .

5 Completeness Theorems for General Quantifier Structures

As Theorem 1 establishes $3$ -SUM as the complete problem for the class $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)$ , we would like to similarly explore complete problems for other quantifier structures. All proofs in this section are deferred to the full version. Let us recall our main geometric problems.

Definition 20 (Verification of $d$ -dimensional Pareto Sum).

Given sets $A,B,C\subseteq\mathbb{Z}^{d}$ . Does the set $C$ dominate $A+B$ , that is does for all $a\in A,b\in B$ exist a $c\in C$ , with $c\geq a+b$ ?

It is easy to see that Verification of $d$ -dimensional Pareto Sum is in $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ .

Definition 21 (Hausdorff Distance under $n$ Translations).

Given sets $A,B,C\subseteq\mathbb{Z}^{d}$ with at most $n$ elements and a $\gamma\in\mathbb{N}$ , the Hausdorff distance under $n$ Translations problem asks whether the following holds:

\delta_{\overrightarrow{H}}^{T(A)}(B,C)\coloneqq\min_{\tau\in A}\delta_{% \overrightarrow{H}}(B,C+\{\tau\})=\min_{\tau\in A}\max_{b\in B}\min_{c\in C}\|% b-(c+\tau)\|_{\infty}\leq\gamma.

We show the following result firstly, which allows us to assume without loss of generality a certain normal form.

Lemma 22.

A general $\mathsf{FOP}_{\mathbb{Z}}(Q_{1}Q_{2}\exists)$ formula, with input set $A_{1}\subseteq\mathbb{Z}^{d_{1}},A_{2}\subseteq\mathbb{Z}^{d_{2}},A_{3}% \subseteq\mathbb{Z}^{d_{3}}$ , where $|A_{1}|=|A_{2}|=|A_{3}|=n$ , can be reduced to the $\mathsf{FOP}_{\mathbb{Z}}(Q_{1}Q_{2}\exists)$ formula

Q_{1}a_{1}^{\prime}\in A_{1}^{\prime}Q_{2}a_{2}^{\prime}\in A_{2}^{\prime}% \exists a_{3}^{\prime}\in A_{3}^{\prime}:a_{1}^{\prime}+a_{2}^{\prime}\leq a_{% 3}^{\prime}

in time $O(n)$ , where $|A_{1}^{\prime}|=|A_{2}^{\prime}|=n$ and $|A_{3}^{\prime}|=O(n)$ .

The above lemma immediately gives us complete syntactic problems for our classes. It remains to establish connections between the different quantifier structure classes, and explore natural variants of the syntactic problems.

The syntactic complete problem for the class $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ turns out to be equivalent to Hausdorff Distance under $n$ Translations. We obtain:

Lemma 23 (Hausdorff Distance under $n$ Translations is complete for $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ ).

There is a function $\epsilon(d)>0$ such that Hausdorff Distance under $n$ Translations can be solved in time $O(n^{2-\epsilon(d)})$ if and only if all problems $P$ in $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ can be solved in time $O(n^{2-\epsilon_{P}})$ for an $\epsilon_{P}>0$ .

Similarly, the Verification of Pareto Sum problem is complete for the class $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ .

Lemma 24 (Verification of Pareto Sum is complete for $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ ).

There is a function $\epsilon(d)>0$ such that Verification of Pareto Sum can be solved in time $O(n^{2-\epsilon(d)})$ if and only if all problems $P$ in $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ can be solved in time $O(n^{2-\epsilon_{P}})$ for an $\epsilon_{P}>0$ .

5.1 $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)\to\mathsf{FOP}_{\mathbb{Z}}(% \exists\exists\exists)$

We continue with handling the class $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)$ . By simply making use of Corollary 19, one can easily prove that $3$ -SUM is hard for the class $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)$ . We can also show a deterministic proof, as Corollary 19 makes use of the subquadratic equivalence between $3$ -SUM and $\#$ All-ints $3$ -SUM, which relies on randomization techniques.

See 9

5.2 $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)\to\mathsf{FOP}_{\mathbb{Z}}(% \forall\forall\exists)$

We explore the connection between the problem Additive Sumset Approximation, which is a member of the class $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ , and the $3$ -SUM problem. The following theorem will play a key role to enable the discovery of the relationship between $3$ -SUM and other quantifier structures. See 10 The proof is deferred to the full version of the paper.

5.3 Completeness results for the class $\mathsf{FOP}_{\mathbb{Z}}^{k}$

We turn to combining the above insights to establish (a pair of) complete problems for the class $\mathsf{FOP}_{\mathbb{Z}}$ . The proofs in this section are deferred to the full version of the paper.

See 11

See 12 We finally obtain our completeness theorem for the whole class $\mathsf{FOP}_{\mathbb{Z}}^{k}$ . See 4

Essentially, these two problems capture the complexity of the class $\mathsf{FOP}_{\mathbb{Z}}^{3}$ and can be seen as the most important problems in $\mathsf{FOP}_{\mathbb{Z}}^{k}$ .

6 The $3$ -SUM problem is complete for $\mathsf{FOP}_{\mathbb{Z}}$ formulas with Inequality Dimension at most 3

In this section, we show that $3$ -SUM problem captures an interesting subclass of $\mathsf{FOP}_{\mathbb{Z}}$ formulas with arbitrary quantifier structure, namely the formulas of sufficiently small inequality dimension. Let us recall the notion of inequality dimension.

Definition 25 (Inequality Dimension of a Formula).

Let $\phi=Q_{1}x_{1}\in A_{1},\dots,Q_{k}x_{k}\in A_{k}:\psi$ be a $\mathsf{FOP}_{\mathbb{Z}}$ formula with $A_{i}\subseteq\mathbb{Z}^{d_{i}}$ .

The inequality dimension of $\phi$ is the smallest number $s$ such that there exists a Boolean function $\psi^{\prime}:\{0,1\}^{s}\to\{0,1\}$ and (strict or non-strict) linear inequalities $L_{1},\dots,L_{s}$ in the variables $\{x_{i}[j]:i\in\{1,\dots,k\},j\in\{1,\dots,d_{i}\}\}$ and the free variables such that $\psi(x_{1},\dots,x_{k})$ is equivalent to $\psi^{\prime}(L_{1},\dots,L_{s})$ .

In the following, we look at the class of problems $\mathsf{FOP}_{\mathbb{Z}}^{k}$ with the restriction of inequality dimension at most $3$ . We use the following naming convention for boxes.

Definition 26.

A $d$ -box in $\mathbb{R}^{d}$ is the cartesian product of $d$ proper intervals $s_{1}\times\dots\times s_{d}$ , where $s_{i}$ is an open, closed or half-open interval. We call a cartesian product of only closed intervals a closed box and a cartesian product of only open intervals an open box.

Given a set $R$ of $n$ closed boxes (represented as $2d$ integer coordinates), and $d$ -dimensional points $a\in A,b\in B$ , we can express in $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)$ whether $a+b$ lies in one of the boxes as follows:

\exists a\in A\exists b\in B\exists r\in R:\bigwedge_{i=1}^{d}r[i]\leq a[i]+b[% i]\land a[i]+b[i]\leq r[d+i].

In fact, we are not limited to closed boxes, if a box is open or half open in a dimension, one can adjust the inequalities in this dimension appropriately.

In order to prove our main theorem in this section, we need to partition the union of $n$ unit cubes in $\mathbb{R}^{3}$ into pairwise interior- and exterior-disjoint boxes. While Chew et al. [23] studied such a decomposition of unit cubes with the requirement of only interior-disjoint boxes, we need an extension of their result to guarantee disjoint exteriors.

Lemma 27 (Disjoint decomposition of the union of cubes in $\mathbb{R}^{3}$ ).

Let $\mathcal{C}$ be a set of $n$ axis-aligned congruent cubes in $\mathbb{R}^{3}$ . The union of these cubes, can be decomposed into $O(n)$ boxes whose interiors and exteriors are disjoint in time $O(n\log^{2}n)$ .

The proof is deferred to the full version.

Theorem 28.

There is an algorithm deciding $3$ -SUM in randomized time $O(n^{2-\epsilon})$ for an $\epsilon>0$ if and only if for each problem $P$ in the classes $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ and $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ of inequality dimension at most $3$ there exists some $\epsilon^{\prime}>0$ such that we can solve $P$ in randomized time $O(n^{2-\epsilon^{\prime}})$ .

Proof.

For the first direction due to Theorem 10, we can reduce $3$ -SUM to an instance of Additive Sumset Approximation,

\forall a\in A\forall b\in B\exists c\in C:c\leq a+b\land a+b\leq c+t,

which has inequality dimension 2. Let us continue with the other direction. Let $\phi:=Q_{1}a\in A\forall b\in B\exists c\in C:\varphi$ , where $Q_{1}\in\{\exists,\forall\}$ and $\varphi$ is a quantifier free linear arithmetic formula with inequality dimension $3$ . Let $L_{1}:=\alpha_{1}^{T}a+\beta_{1}^{T}b\leq\gamma_{1}^{T}c+S_{1}$ , $L_{2}:=\alpha_{2}^{T}a+\beta_{2}^{T}b\leq\gamma_{2}^{T}c+S_{2}$ and $L_{3}:=\alpha_{3}^{T}a+\beta_{3}^{T}b\leq\gamma_{3}^{T}c+S_{3}$ after replacing the free variables. Assume that the formula $\varphi$ is given in DNF, thus each co-clause has at most $3$ atoms, chosen from $L_{1},L_{2},L_{3}$ and their negations. Let

\displaystyle A^{\prime}:=\left\{\left(\begin{array}[]{cc}\alpha_{1}^{T}a\\ \alpha_{2}^{T}a\\ \alpha_{3}^{T}a\end{array}\right):a\in A\right\},B^{\prime}:=\left\{\left(% \begin{array}[]{cc}\beta_{1}^{T}b\\ \beta_{2}^{T}b\\ \beta_{3}^{T}b\end{array}\right):b\in B\right\},C^{\prime}:=\left\{\left(% \begin{array}[]{cc}\gamma_{1}^{T}c+S_{1}\\ \gamma_{2}^{T}c+S_{2}\\ \gamma_{3}^{T}c+S_{3}\end{array}\right):c\in C\right\}

Thus each co-clause consists of conjunctions of a subset of the following set

	$\displaystyle\{$	$\displaystyle a^{\prime}[0]+b^{\prime}[0]\leq c^{\prime}[0],a^{\prime}[0]+b^{% \prime}[0]\geq c^{\prime}[0]+1,a^{\prime}[1]+b^{\prime}[1]\leq c^{\prime}[1],$
		$\displaystyle a^{\prime}[1]+b^{\prime}[1]\geq c^{\prime}[1]+1,a^{\prime}[2]+b^% {\prime}[2]\leq c^{\prime}[2],a^{\prime}[2]+b^{\prime}[2]\geq c^{\prime}[2]+1\}.$

Let the co-clauses of $\varphi$ be $V_{1},\dots,V_{h}$ . Thus, we aim to decide a formula of the form:

Q_{1}a^{\prime}\in A^{\prime}\forall b^{\prime}\in B^{\prime}\exists c^{\prime% }\in C^{\prime}:\bigvee_{i=1}^{h}V_{i}

(2)

For each co-clause $V_{i}$ , $i\in\{1,\dots,h\}$ it holds that $V_{i}$ is of the form

\bigwedge_{k\in V_{i}^{K}}L_{k}\land\bigwedge_{j\in V_{i}^{J}}\lnot L_{j},

for some $V_{i}^{J},V_{i}^{K}\subseteq\{1,2,3\}$ and $V_{i}^{J}\cap V_{i}^{K}=\emptyset$ .

Let us consider for each fixed $c^{\prime}\in C^{\prime}$ the following possibly empty orthant in $\mathbb{R}^{3}$ .

\mathcal{S}(V_{i},c^{\prime}):=\{x\in\mathbb{R}^{3}:\bigwedge_{k\in V_{i}^{K}}% x[k]\leq c^{\prime}[k]\land\bigwedge_{j\in V_{i}^{J}}x[j]\geq c^{\prime}[j]+1\}.

By construction, it is immediate that for a fixed $c^{\prime}$ and $(a^{\prime},b^{\prime})\in A^{\prime}\times B^{\prime}$ that $(a^{\prime},b^{\prime},c^{\prime})$ fulfill the co-clause $V_{i}$ if and only if $a^{\prime}+b^{\prime}\in\mathcal{S}(V_{i},c^{\prime})$ . Thus, equivalently to (2), we ask

Q_{1}a^{\prime}\in A^{\prime}\forall b^{\prime}\in B^{\prime}\exists c^{\prime% }\in C^{\prime}:\bigvee_{i=1}^{h}\left(a^{\prime}+b^{\prime}\in S(V_{i},c^{% \prime})\right).

Having a closer look, $\bigvee_{i=1}^{h}\left(a^{\prime}+b^{\prime}\in S(V_{i},c^{\prime})\right)$ is true if and only if $a^{\prime}+b^{\prime}$ lies in one of the orthants $S(V_{i},c^{\prime})$ .

We argue that we may represent the orthant $\mathcal{S}(V_{i},c^{\prime})$ as an appropriately chosen cube in $\mathbb{R}^{3}$ . To this end, let $M:=2\cdot\max\{\|a\|_{1}+\|b\|_{1}+\|c\|_{1}:a^{\prime}\in A^{\prime},b^{% \prime}\in B^{\prime},c^{\prime}\in C^{\prime}\}$ be a sufficiently large number. We can interpret $\mathcal{S}(V_{i},c^{\prime})$ as a cube of the type $\mathcal{C}_{i,c^{\prime}}=[m_{0},m^{\prime}_{0}]\times[m_{1},m_{1}^{\prime}]% \times[m_{2},m^{\prime}_{2}]$ , where for $u\in\{0,1,2\}$ , we define:

\displaystyle m_{u}:=\begin{cases}-M&u\not\in V_{i}^{K},u\not\in V_{i}^{J},\\ -2M+c[u]&u\in V_{i}^{K},\\ c[u]+1&u\in V_{i}^{J},\end{cases}\quad m_{u}^{\prime}:=\begin{cases}M&u\not\in V% _{i}^{K},u\not\in V_{i}^{J},\\ c[u]&u\in V_{i}^{K},\\ 2M+c[u]+1&u\in V_{i}^{J}.\end{cases}

The cubes are axis-aligned and have side length $2M$ . Due to the large size of the cube we get for fixed $c^{\prime}\in C^{\prime}$ that $a^{\prime}+b^{\prime}\in\mathcal{S}(V_{i},c^{\prime})$ if and only if $a^{\prime}+b^{\prime}$ lies inside the cube $\mathcal{C}_{i,c^{\prime}}$ .

By Lemma 27, we can decompose the collection of cubes $\mathcal{C}_{i,c^{\prime}}$ for $i\in\{1,\dots,H\},c^{\prime}\in C^{\prime}$ into $l=O(n)$ disjoint boxes $\mathcal{R}:=\{R_{1},\dots,R_{l}\}$ in time $O(n\log^{2}n)$ . Let us now go through a case distinction based on the first quantifier.

$\blacksquare$

If $Q_{1}=\forall$ , equivalent to $\phi$ we ask

$\forall a^{\prime}\in A^{\prime}\forall b^{\prime}\in B^{\prime}\exists i\in\{% 1,\dots,l\}:a^{\prime}+b^{\prime}\text{ lies in }R_{i}.$

By replacing each $i\in\{1,\dots,l\}$ by a 6-tuple denoting the dimensions of the box $R_{i}$ , we can reduce counting the number of $(a^{\prime},b^{\prime},R_{i})$ with $a^{\prime}+b^{\prime}\in R_{i}$ to 3-SUM using Corollary 3. Due to the disjointness of the boxes $R_{i}$ , we know that no $(a^{\prime},b^{\prime})$ can be in different boxes $R_{i},R_{i^{\prime}}$ with $i\neq i^{\prime}$ .

Thus, we can decide our original question by checking whether the number of such witnesses equals $|A^{\prime}|\cdot|B^{\prime}|$ , concluding the fine-grained reduction to 3-SUM.
$\blacksquare$

Assume now that $Q_{1}=\exists$ . Thus, equivalently to $\phi$ , we ask.

$\exists a^{\prime}\in A^{\prime}\forall b^{\prime}\in B^{\prime}\exists i\in\{% 1,\dots,l\}:a^{\prime}+b^{\prime}\text{ lies in }R_{i}.$

We can now make use of Corollary 19. Count for each $a^{\prime}\in A^{\prime}$ the number of witnesses $(a^{\prime},b^{\prime},R_{i})$ with $a^{\prime}+b^{\prime}\in R^{\prime}$ . We claim that it remains to check whether there is some $a^{\prime}$ that is involved in $|B^{\prime}|$ witnesses. To see this, note that due to the disjointness of the $R_{i}$ ’s, for any $a^{\prime}\in A^{\prime}$ we have that the number of $(b^{\prime},R_{i})$ with $a^{\prime}+b^{\prime}\in R_{i}$ is equal to the number of $b^{\prime}$ such that there exists $R_{i}$ with $a^{\prime}+b^{\prime}\in R_{i}$ . Again, the desired reduction to 3-SUM follows.

$\hfill\blacktriangleleft$

We remark that, by [11], we know that the complexity of the union of orthants in $\mathbb{R}^{d}$ has worst case complexity $O(n^{\lfloor d/2\rfloor})$ . Thus, the above proof does not seem directly generalizable to inequality dimensions larger than 3. We can extend Theorem 28 to $k$ -quantifiers by the following theorem.

See 5

The above theorem gives us immediate reductions to $3$ -SUM for many seemingly unrelated problems of different quantifier structures and semantics.

For instance, as a direct application of the above theorem we can conclude the equivalence of the Additive Sumset Approximation problem to $3$ -SUM, together with Theorem 10.

Lemma 29 (Additive Sumset Approximation $\leq_{2}$ $3$ -SUM).

If the $3$ -SUM problem can be solved in randomized time $O(n^{2-\epsilon})$ for an $\epsilon>0$ then Additive Sumset Approximation problem can be solved in randomized time $O(n^{2-\epsilon^{\prime}})$ for an $\epsilon^{\prime}>0$ .

7 Application: A lower bound on the computation of Pareto Sums

In the following, we explore how the $3$ -SUM hardness of Verification of Pareto Sum translates to a hardness result for the problem of computing Pareto Sums. Let us first justify the naming of the Verification of Pareto Sum problem, by showing it to be subquadratic equivalent to the more natural extended version of Verification of Pareto Sum. Throughout this section, we consider dimensions $d\geq 2$ .

Definition 30 (Verification of Pareto Sum (Extended version)).

Given sets $A,B,C\subseteq\mathbb{Z}^{d}$ , do the following properties hold simultaneously:

$\blacksquare$

(Inclusion): $C\subseteq A+B$ ,
$\blacksquare$

(Dominance): $C$ dominates $A+B$ . More formally, for every $a\in A,b\in B$ there exists $c\in C$ with $c\geq a+b$ .
$\blacksquare$

(Minimality): There are no $c,c^{\prime}\in C$ with $c\neq c^{\prime}$ and $c\leq c^{\prime}$ .

We make use of the following lemma and its construction for the results in this section.

Lemma 31.

Given sets $A,B,C\subseteq\mathbb{Z}^{d}$ of size at most $n$ , one can construct sets $\tilde{A},\tilde{B},\tilde{C}\subseteq\mathbb{Z}^{d}$ of size $\Theta(n)$ in time $\tilde{O}(n)$ such that (1) $\tilde{A},\tilde{B},\tilde{C}$ always satisfy the minimality and inclusion condition and (2) $\tilde{A},\tilde{B},\tilde{C}$ fulfill the dominance condition if and only if $A, B, C$ fulfill the dominance condition.

Due to space constraints, the proof had to be deferred to the full version. Using this construction, it is not difficult to obtain the following equivalence.

Lemma 32.

There is an $O(n^{2-\epsilon})$ time algorithm for an $\epsilon>0$ for Verification of Pareto Sum (Extended Version) if and only if there is an $O(n^{2-\epsilon^{\prime}})$ time algorithm for an $\epsilon^{\prime}>0$ for Verification of Pareto Sum.

The proof can be found in the full version. Thus, for subquadratic reductions, we can restrict ourselves to the Verification of Pareto Sum problem, which essentially only checks the dominance condition.

Let us now consider the natural problem of computing the Pareto Sum.

Definition 33 (Pareto Sum).

Given sets $A,B\subseteq\mathbb{Z}^{d}$ , compute a set $C\subseteq\mathbb{Z}$ , such that $A, B, C$ satisfy the Inclusion, Dominance and Minimality condition.

In the following, we argue why the lower bounds to Verification of Pareto Sum translate to lower bounds to Computation of the Pareto Sum. Formally, we prove:

Lemma 34.

If there is an algorithm to compute the Pareto Sum $C$ of sets $A,B\subseteq\mathbb{Z}^{d}$ in time $O(n^{2-\epsilon})$ for an $\epsilon>0$ even when $C=\Theta(n)$ , then one can also decide Verification of Pareto Sum of sets $A, B, C$ in time $O(n^{2-\epsilon^{\prime}})$ for an $\epsilon^{\prime}>0$ .

We conclude this section with our resulting hardness results for computing Pareto Sums. See 7

8 Future Work

While we exhibit a pair of problems that is complete for the class $\mathsf{FOP}_{\mathbb{Z}}$ , one could still ask whether there is a subquadratic reduction from Hausdorff distance under $n$ Translations to Verification of Pareto Sum. As a result there would be a single complete problem (or rather the canonical multidimensional family of a single geometric problem) for $\mathsf{FOP}_{\mathbb{Z}}$ .

Is Verification of Pareto Sum complete for the class $\mathsf{FOP}_{\mathbb{Z}}$ ?

Interestingly, previous completeness theorems [36] were able to establish a problem of quantifier structure $\forall\forall\exists$ (the Orthogonal Vectors problem) as complete by making use of a technique in [51] that was originally used to show subcubic equivalence between All-Pairs Negative Triangle and Negative Triangle. However, a major problem we encounter is that while the third quantifier in the Orthogonal Vectors problem ranges over a sparse (intuitively: subpolynomially sized) domain (i.e., the dimensions of the vectors), the third quantifier in Pareto Sum Verification ranges over a linearly sized domain (i.e., the set $C$ ).

Finally, we ask if our $3$ -SUM completeness result for arbitrary quantifier structures can be improved upon.

Can we establish a $d>3$ such that $3$ -SUM is complete for $\mathsf{FOP}_{\mathbb{Z}}$ formulas of inequality dimension at most $d$ ?

References

[1] Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann. Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 192–203. IEEE Computer Society, 2017. doi:10.1109/FOCS.2017.26.
[2] Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann. Impossibility results for grammar-compressed linear algebra. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/645e6bfdd05d1a69c5e47b20f0a91d46-Abstract.html.
[3] Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir. Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1487–1500. ACM, 2022. doi:10.1145/3519935.3520066.
[4] Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 1–12. Springer, 2013. doi:10.1007/978-3-642-39206-1_1.
[5] Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 1–12. Springer, 2014. doi:10.1007/978-3-662-44777-2_1.
[6] Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.53.
[7] Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, and Maria Paula Parga Nina. The fine-grained complexity of multi-dimensional ordering properties. Algorithmica, 84(11):3156–3191, 2022. doi:10.1007/S00453-022-01014-X.
[8] Christian Artigues, Marie-José Huguet, Fallou Gueye, Frédéric Schettini, and Laurent Dezou. State-based accelerations and bidirectional search for bi-objective multi-modal shortest paths. Transportation Research Part C: Emerging Technologies, 27:233–259, 2013.
[9] Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. Better approximations for tree sparsity in nearly-linear time. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2215–2229. SIAM, 2017. doi:10.1137/1.9781611974782.145.
[10] Stephen A Bloch, Jonathan F Buss, and Judy Goldsmith. How hard are n 2-hard problems? ACM SIGACT News, 25(2):83–85, 1994. doi:10.1145/181462.181465.
[11] Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discret. Comput. Geom., 19(4):485–519, 1998. doi:10.1007/PL00009366.
[12] Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann. Fine-grained completeness for optimization in P. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), volume 207 of LIPIcs, pages 9:1–9:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.APPROX/RANDOM.2021.9.
[13] Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann. A structural investigation of the approximability of polynomial-time problems. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 30:1–30:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.ICALP.2022.30.
[14] Karl Bringmann, Nick Fischer, and Marvin Künnemann. A fine-grained analogue of schaefer’s theorem in P: dichotomy of existsˆk-forall-quantified first-order graph properties. In Amir Shpilka, editor, 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pages 31:1–31:27. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.CCC.2019.31.
[15] Karl Bringmann, Nick Fischer, and Vasileios Nakos. Sparse nonnegative convolution is equivalent to dense nonnegative convolution. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1711–1724. ACM, 2021. doi:10.1145/3406325.3451090.
[16] Karl Bringmann, Nick Fischer, and Vasileios Nakos. Deterministic and las vegas algorithms for sparse nonnegative convolution. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 3069–3090. SIAM, 2022. doi:10.1137/1.9781611977073.119.
[17] Karl Bringmann and Vasileios Nakos. Fast n-fold boolean convolution via additive combinatorics. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 41:1–41:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.ICALP.2021.41.
[18] Karl Bringmann and André Nusser. Translating hausdorff is hard: Fine-grained lower bounds for hausdorff distance under translation. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference), volume 189 of LIPIcs, pages 18:1–18:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.SOCG.2021.18.
[19] Timothy M. Chan. Minimum l_ $\infty$ hausdorff distance of point sets under translation: Generalizing klee’s measure problem. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 of LIPIcs, pages 24:1–24:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.SOCG.2023.24.
[20] Timothy M. Chan and Moshe Lewenstein. Clustered integer 3sum via additive combinatorics. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 31–40. ACM, 2015. doi:10.1145/2746539.2746568.
[21] Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Hardness for triangle problems under even more believable hypotheses: reductions from real apsp, real 3sum, and OV. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1501–1514. ACM, 2022. doi:10.1145/3519935.3520032.
[22] Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Fredman’s trick meets dominance product: Fine-grained complexity of unweighted apsp, 3sum counting, and more. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 419–432. ACM, 2023. doi:10.1145/3564246.3585237.
[23] L. Paul Chew, Dorit Dor, Alon Efrat, and Klara Kedem. Geometric pattern matching in d -dimensional space. Discret. Comput. Geom., 21(2):257–274, 1999. doi:10.1007/PL00009420.
[24] L Paul Chew and Klara Kedem. Improvements on geometric pattern matching problems. In Algorithm Theory—SWAT’92: Third Scandinavian Workshop on Algorithm Theory Helsinki, Finland, July 8–10, 1992 Proceedings 3, pages 318–325. Springer, 1992. doi:10.1007/3-540-55706-7_28.
[25] L. Paul Chew and Klara Kedem. Improvements on geometric pattern matching problems. In Otto Nurmi and Esko Ukkonen, editors, Algorithm Theory - SWAT ’92, Third Scandinavian Workshop on Algorithm Theory, Helsinki, Finland, July 8-10, 1992, Proceedings, volume 621 of Lecture Notes in Computer Science, pages 318–325. Springer, 1992. doi:10.1007/3-540-55706-7_28.
[26] Richard Cole and Ramesh Hariharan. Verifying candidate matches in sparse and wildcard matching. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 592–601. ACM, 2002. doi:10.1145/509907.509992.
[27] Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms, 15(1):14:1–14:25, 2019. doi:10.1145/3293465.
[28] Holger Dell, Marc Roth, and Philip Wellnitz. Counting answers to existential questions. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 113:1–113:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ICALP.2019.113.
[29] Bartlomiej Dudek, Pawel Gawrychowski, and Tatiana Starikovskaya. All non-trivial variants of 3-ldt are equivalent. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 974–981. ACM, 2020. doi:10.1145/3357713.3384275.
[30] Matthias Ehrgott and Xavier Gandibleux. A survey and annotated bibliography of multiobjective combinatorial optimization. OR-spektrum, 22:425–460, 2000. doi:10.1007/S002910000046.
[31] Jeff Erickson. New lower bounds for convex hull problems in odd dimensions. SIAM J. Comput., 28(4):1198–1214, 1999. doi:10.1137/S0097539797315410.
[32] Nick Fischer, Marvin Künnemann, and Mirza Redzic. The effect of sparsity on k-dominating set and related first-order graph properties. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4704–4727. SIAM, 2024. doi:10.1137/1.9781611977912.168.
[33] Daniel Funke, Demian Hespe, Peter Sanders, Sabine Storandt, and Carina Truschel. Pareto sums of pareto sets: Lower bounds and algorithms. CoRR, abs/2409.10232, 2024. doi:10.48550/arXiv.2409.10232.
[34] Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan. Scaling and related techniques for geometry problems. In Richard A. DeMillo, editor, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 135–143. ACM, 1984. doi:10.1145/800057.808675.
[35] Anka Gajentaan and Mark H. Overmars. On a class of o(n2) problems in computational geometry. Comput. Geom., 5:165–185, 1995. doi:10.1016/0925-7721(95)00022-2.
[36] Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms, 15(2):23:1–23:35, 2019. doi:10.1145/3196275.
[37] Demian Hespe, Peter Sanders, Sabine Storandt, and Carina Truschel. Pareto sums of pareto sets. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 60:1–60:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ESA.2023.60.
[38] Daniel P. Huttenlocher and Klara Kedem. Computing the minimum hausdorff distance for point sets under translation. In Raimund Seidel, editor, Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990, pages 340–349. ACM, 1990. doi:10.1145/98524.98599.
[39] Zahra Jafargholi and Emanuele Viola. 3sum, 3xor, triangles. Algorithmica, 74(1):326–343, 2016. doi:10.1007/S00453-014-9946-9.
[40] Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1272–1287. SIAM, 2016. doi:10.1137/1.9781611974331.CH89.
[41] Marvin Künnemann. A tight (non-combinatorial) conditional lower bound for klee’s measure problem in 3d. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 555–566. IEEE, 2022. doi:10.1109/FOCS54457.2022.00059.
[42] Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic time-space trade-offs for k-sum. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 58:1–58:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.ICALP.2016.58.
[43] Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236–1252. SIAM, 2018. doi:10.1137/1.9781611975031.80.
[44] Thibaut Lust and Daniel Tuyttens. Variable and large neighborhood search to solve the multiobjective set covering problem. Journal of Heuristics, 20:165–188, 2014. doi:10.1007/S10732-013-9236-8.
[45] André Nusser. Fine-grained complexity and algorithm engineering of geometric similarity measures. PhD thesis, Saarland University, Saarbrücken, Germany, 2021. URL: https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/33904.
[46] Mihai Puatracscu. Towards polynomial lower bounds for dynamic problems. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603–610. ACM, 2010. doi:10.1145/1806689.1806772.
[47] Britta Schulze, Kathrin Klamroth, and Michael Stiglmayr. Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions. Journal of Global Optimization, 74(3):495–522, 2019. doi:10.1007/S10898-019-00745-6.
[48] Carola Wenk. Shape matching in higher dimensions. PhD thesis, Free University of Berlin, Dahlem, Germany, 2003. URL: http://www.diss.fu-berlin.de/2003/151/index.html.
[49] Ryan Williams. Faster decision of first-order graph properties. In Thomas A. Henzinger and Dale Miller, editors, Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS ’14, Vienna, Austria, July 14 - 18, 2014, pages 80:1–80:6. ACM, 2014. doi:10.1145/2603088.2603121.
[50] Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the international congress of mathematicians: Rio de janeiro 2018, pages 3447–3487. World Scientific, 2018.
[51] Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645–654. IEEE Computer Society, 2010. doi:10.1109/FOCS.2010.67.
[52] Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831–854, 2013. doi:10.1137/09076619X.

[bib.bib1] [1] Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann. Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 192–203. IEEE Computer Society, 2017. doi:10.1109/FOCS.2017.26.

[bib.bib2] [2] Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann. Impossibility results for grammar-compressed linear algebra. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/645e6bfdd05d1a69c5e47b20f0a91d46-Abstract.html.

[bib.bib3] [3] Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir. Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1487–1500. ACM, 2022. doi:10.1145/3519935.3520066.

[bib.bib4] [4] Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 1–12. Springer, 2013. doi:10.1007/978-3-642-39206-1_1.

[bib.bib5] [5] Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 1–12. Springer, 2014. doi:10.1007/978-3-662-44777-2_1.

[bib.bib6] [6] Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.53.

[bib.bib7] [7] Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, and Maria Paula Parga Nina. The fine-grained complexity of multi-dimensional ordering properties. Algorithmica, 84(11):3156–3191, 2022. doi:10.1007/S00453-022-01014-X.

[bib.bib8] [8] Christian Artigues, Marie-José Huguet, Fallou Gueye, Frédéric Schettini, and Laurent Dezou. State-based accelerations and bidirectional search for bi-objective multi-modal shortest paths. Transportation Research Part C: Emerging Technologies, 27:233–259, 2013.

[bib.bib9] [9] Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. Better approximations for tree sparsity in nearly-linear time. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2215–2229. SIAM, 2017. doi:10.1137/1.9781611974782.145.

[bib.bib10] [10] Stephen A Bloch, Jonathan F Buss, and Judy Goldsmith. How hard are n 2-hard problems? ACM SIGACT News, 25(2):83–85, 1994. doi:10.1145/181462.181465.

[bib.bib11] [11] Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discret. Comput. Geom., 19(4):485–519, 1998. doi:10.1007/PL00009366.

[bib.bib12] [12] Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann. Fine-grained completeness for optimization in P. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), volume 207 of LIPIcs, pages 9:1–9:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.APPROX/RANDOM.2021.9.

[bib.bib13] [13] Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann. A structural investigation of the approximability of polynomial-time problems. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 30:1–30:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.ICALP.2022.30.

[bib.bib14] [14] Karl Bringmann, Nick Fischer, and Marvin Künnemann. A fine-grained analogue of schaefer’s theorem in P: dichotomy of existsˆk-forall-quantified first-order graph properties. In Amir Shpilka, editor, 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pages 31:1–31:27. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.CCC.2019.31.

[bib.bib15] [15] Karl Bringmann, Nick Fischer, and Vasileios Nakos. Sparse nonnegative convolution is equivalent to dense nonnegative convolution. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1711–1724. ACM, 2021. doi:10.1145/3406325.3451090.

[bib.bib16] [16] Karl Bringmann, Nick Fischer, and Vasileios Nakos. Deterministic and las vegas algorithms for sparse nonnegative convolution. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 3069–3090. SIAM, 2022. doi:10.1137/1.9781611977073.119.

[bib.bib17] [17] Karl Bringmann and Vasileios Nakos. Fast n-fold boolean convolution via additive combinatorics. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 41:1–41:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.ICALP.2021.41.

[bib.bib18] [18] Karl Bringmann and André Nusser. Translating hausdorff is hard: Fine-grained lower bounds for hausdorff distance under translation. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference), volume 189 of LIPIcs, pages 18:1–18:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.SOCG.2021.18.

[bib.bib19] [19] Timothy M. Chan. Minimum l_ $\infty$ hausdorff distance of point sets under translation: Generalizing klee’s measure problem. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 of LIPIcs, pages 24:1–24:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.SOCG.2023.24.

[bib.bib20] [20] Timothy M. Chan and Moshe Lewenstein. Clustered integer 3sum via additive combinatorics. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 31–40. ACM, 2015. doi:10.1145/2746539.2746568.

[bib.bib21] [21] Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Hardness for triangle problems under even more believable hypotheses: reductions from real apsp, real 3sum, and OV. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1501–1514. ACM, 2022. doi:10.1145/3519935.3520032.

[bib.bib22] [22] Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Fredman’s trick meets dominance product: Fine-grained complexity of unweighted apsp, 3sum counting, and more. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 419–432. ACM, 2023. doi:10.1145/3564246.3585237.

[bib.bib23] [23] L. Paul Chew, Dorit Dor, Alon Efrat, and Klara Kedem. Geometric pattern matching in d -dimensional space. Discret. Comput. Geom., 21(2):257–274, 1999. doi:10.1007/PL00009420.

[bib.bib24] [24] L Paul Chew and Klara Kedem. Improvements on geometric pattern matching problems. In Algorithm Theory—SWAT’92: Third Scandinavian Workshop on Algorithm Theory Helsinki, Finland, July 8–10, 1992 Proceedings 3, pages 318–325. Springer, 1992. doi:10.1007/3-540-55706-7_28.

[bib.bib25] [25] L. Paul Chew and Klara Kedem. Improvements on geometric pattern matching problems. In Otto Nurmi and Esko Ukkonen, editors, Algorithm Theory - SWAT ’92, Third Scandinavian Workshop on Algorithm Theory, Helsinki, Finland, July 8-10, 1992, Proceedings, volume 621 of Lecture Notes in Computer Science, pages 318–325. Springer, 1992. doi:10.1007/3-540-55706-7_28.

[bib.bib26] [26] Richard Cole and Ramesh Hariharan. Verifying candidate matches in sparse and wildcard matching. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 592–601. ACM, 2002. doi:10.1145/509907.509992.

[bib.bib27] [27] Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms, 15(1):14:1–14:25, 2019. doi:10.1145/3293465.

[bib.bib28] [28] Holger Dell, Marc Roth, and Philip Wellnitz. Counting answers to existential questions. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 113:1–113:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ICALP.2019.113.

[bib.bib29] [29] Bartlomiej Dudek, Pawel Gawrychowski, and Tatiana Starikovskaya. All non-trivial variants of 3-ldt are equivalent. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 974–981. ACM, 2020. doi:10.1145/3357713.3384275.

[bib.bib30] [30] Matthias Ehrgott and Xavier Gandibleux. A survey and annotated bibliography of multiobjective combinatorial optimization. OR-spektrum, 22:425–460, 2000. doi:10.1007/S002910000046.

[bib.bib31] [31] Jeff Erickson. New lower bounds for convex hull problems in odd dimensions. SIAM J. Comput., 28(4):1198–1214, 1999. doi:10.1137/S0097539797315410.

[bib.bib32] [32] Nick Fischer, Marvin Künnemann, and Mirza Redzic. The effect of sparsity on k-dominating set and related first-order graph properties. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4704–4727. SIAM, 2024. doi:10.1137/1.9781611977912.168.

[bib.bib33] [33] Daniel Funke, Demian Hespe, Peter Sanders, Sabine Storandt, and Carina Truschel. Pareto sums of pareto sets: Lower bounds and algorithms. CoRR, abs/2409.10232, 2024. doi:10.48550/arXiv.2409.10232.

[bib.bib34] [34] Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan. Scaling and related techniques for geometry problems. In Richard A. DeMillo, editor, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 135–143. ACM, 1984. doi:10.1145/800057.808675.

[bib.bib35] [35] Anka Gajentaan and Mark H. Overmars. On a class of o(n2) problems in computational geometry. Comput. Geom., 5:165–185, 1995. doi:10.1016/0925-7721(95)00022-2.

[bib.bib36] [36] Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms, 15(2):23:1–23:35, 2019. doi:10.1145/3196275.

[bib.bib37] [37] Demian Hespe, Peter Sanders, Sabine Storandt, and Carina Truschel. Pareto sums of pareto sets. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 60:1–60:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ESA.2023.60.

[bib.bib38] [38] Daniel P. Huttenlocher and Klara Kedem. Computing the minimum hausdorff distance for point sets under translation. In Raimund Seidel, editor, Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990, pages 340–349. ACM, 1990. doi:10.1145/98524.98599.

[bib.bib39] [39] Zahra Jafargholi and Emanuele Viola. 3sum, 3xor, triangles. Algorithmica, 74(1):326–343, 2016. doi:10.1007/S00453-014-9946-9.

[bib.bib40] [40] Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1272–1287. SIAM, 2016. doi:10.1137/1.9781611974331.CH89.

[bib.bib41] [41] Marvin Künnemann. A tight (non-combinatorial) conditional lower bound for klee’s measure problem in 3d. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 555–566. IEEE, 2022. doi:10.1109/FOCS54457.2022.00059.

[bib.bib42] [42] Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic time-space trade-offs for k-sum. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 58:1–58:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.ICALP.2016.58.

[bib.bib43] [43] Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236–1252. SIAM, 2018. doi:10.1137/1.9781611975031.80.

[bib.bib44] [44] Thibaut Lust and Daniel Tuyttens. Variable and large neighborhood search to solve the multiobjective set covering problem. Journal of Heuristics, 20:165–188, 2014. doi:10.1007/S10732-013-9236-8.

[bib.bib45] [45] André Nusser. Fine-grained complexity and algorithm engineering of geometric similarity measures. PhD thesis, Saarland University, Saarbrücken, Germany, 2021. URL: https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/33904.

[bib.bib46] [46] Mihai Puatracscu. Towards polynomial lower bounds for dynamic problems. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603–610. ACM, 2010. doi:10.1145/1806689.1806772.

[bib.bib47] [47] Britta Schulze, Kathrin Klamroth, and Michael Stiglmayr. Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions. Journal of Global Optimization, 74(3):495–522, 2019. doi:10.1007/S10898-019-00745-6.

[bib.bib48] [48] Carola Wenk. Shape matching in higher dimensions. PhD thesis, Free University of Berlin, Dahlem, Germany, 2003. URL: http://www.diss.fu-berlin.de/2003/151/index.html.

[bib.bib49] [49] Ryan Williams. Faster decision of first-order graph properties. In Thomas A. Henzinger and Dale Miller, editors, Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS ’14, Vienna, Austria, July 14 - 18, 2014, pages 80:1–80:6. ACM, 2014. doi:10.1145/2603088.2603121.

[bib.bib50] [50] Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the international congress of mathematicians: Rio de janeiro 2018, pages 3447–3487. World Scientific, 2018.

[bib.bib51] [51] Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645–654. IEEE Computer Society, 2010. doi:10.1109/FOCS.2010.67.

[bib.bib52] [52] Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831–854, 2013. doi:10.1137/09076619X.

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our approach

1.2 Our Contributions

1.2.1 𝒌-SUM is complete for the existential fragment of 𝗙𝗢𝗣ℤ

Theorem 1 (k-SUM is 𝖥𝖮𝖯ℤ⁢(∃k)-complete).

1.2.2 Completeness for counting witnesses

Theorem 2.

Corollary 3.

1.2.3 Completeness for general quantifier structures of 𝗙𝗢𝗣ℤ

Hausdorff Distance under 𝒏 Translations

Verification of Pareto Sums

A problem pair that is complete for 𝗙𝗢𝗣ℤ

Theorem 4.

1.2.4 𝟑-SUM is complete for 𝗙𝗢𝗣ℤ formulas of low inequality dimension

Theorem 5.

Further Applications

Theorem 6.

Theorem 7 (Pareto Sum Computation Lower Bound).

1.3 Further Related Work

2 Technical Overview

Completeness of 𝒌-SUM for 𝗙𝗢𝗣ℤ⁢(∃𝒌)

Counting witnesses and handling multisets

On general quantifier structures

Lemma 8 (Syntactic Complete problems (Informal Version)).

On the quantifier change 𝗙𝗢𝗣ℤ⁢(∀∃∃)→𝗙𝗢𝗣ℤ⁢(∃∃∃)

Lemma 9.

On the quantifier change 𝗙𝗢𝗣ℤ⁢(∃∃∃)→𝗙𝗢𝗣ℤ⁢(∀∀∃)

Theorem 10.

On completeness results for 𝗙𝗢𝗣ℤ𝒌

Lemma 11.

Lemma 12.

The 𝟑-SUM completeness of formulas with inequality dimension at most 𝟑

3 𝒌-SUM is complete for existential 𝗙𝗢𝗣ℤ formulas

Lemma 13.

4 On counting witnesses in 𝗙𝗢𝗣ℤ

Definition 14 ((U,d)-vector Multiset #⁢k-SUM).

Lemma 15 ((U,d)-vector Multiset #⁢k-SUM ≤⌈k/2⌉ Multiset #⁢k-SUM).

Lemma 16 (M-multiplicity #⁢k-SUM≤⌈k/2⌉ #⁢k-SUM).

Observation 17.

Lemma 18.

Proof.

Corollary 19.

5 Completeness Theorems for General Quantifier Structures

Definition 20 (Verification of d-dimensional Pareto Sum).

Definition 21 (Hausdorff Distance under n Translations).

Lemma 22.

Lemma 23 (Hausdorff Distance under n Translations is complete for 𝖥𝖮𝖯ℤ⁢(∃∀∃)).

Lemma 24 (Verification of Pareto Sum is complete for 𝖥𝖮𝖯ℤ⁢(∀∀∃)).

5.1 𝗙𝗢𝗣ℤ⁢(∀∃∃)→𝗙𝗢𝗣ℤ⁢(∃∃∃)

5.2 𝗙𝗢𝗣ℤ⁢(∃∃∃)→𝗙𝗢𝗣ℤ⁢(∀∀∃)

5.3 Completeness results for the class 𝗙𝗢𝗣ℤ𝒌

6 The 𝟑-SUM problem is complete for 𝗙𝗢𝗣ℤ formulas with Inequality Dimension at most 3

Definition 25 (Inequality Dimension of a Formula).

Definition 26.

Lemma 27 (Disjoint decomposition of the union of cubes in ℝ3).

Theorem 28.

Proof.

Lemma 29 (Additive Sumset Approximation ≤2 3-SUM).

7 Application: A lower bound on the computation of Pareto Sums

Definition 30 (Verification of Pareto Sum (Extended version)).

Lemma 31.

Lemma 32.

Definition 33 (Pareto Sum).

Lemma 34.

8 Future Work

References

Completeness Theorems for $k$ -SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic

1.2.1 $𝒌$ -SUM is complete for the existential fragment of $\mathsf{FOP}_{\mathbb{Z}}$

Theorem 1 ( $k$ -SUM is $\mathsf{FOP}_{\mathbb{Z}}(\exists^{k})$ -complete).

1.2.3 Completeness for general quantifier structures of $\mathsf{FOP}_{\mathbb{Z}}$

Hausdorff Distance under $𝒏$ Translations

A problem pair that is complete for $\mathsf{FOP}_{\mathbb{Z}}$

1.2.4 $3$ -SUM is complete for $\mathsf{FOP}_{\mathbb{Z}}$ formulas of low inequality dimension

Completeness of $𝒌$ -SUM for $\mathsf{FOP_{\mathbb{Z}}}(\exists^{k})$

On the quantifier change $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)\to\mathsf{FOP}_{\mathbb{Z}}(% \exists\exists\exists)$

On the quantifier change $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)\to\mathsf{FOP}_{\mathbb{Z}}(% \forall\forall\exists)$

On completeness results for $\mathsf{FOP}_{\mathbb{Z}}^{k}$

The $3$ -SUM completeness of formulas with inequality dimension at most $3$

3 $𝒌$ -SUM is complete for existential $\mathsf{FOP}_{\mathbb{Z}}$ formulas

4 On counting witnesses in $\mathsf{FOP}_{\mathbb{Z}}$

Definition 14 ( $(U,d)$ -vector Multiset $\#k$ -SUM).

Lemma 15 ( $(U,d)$ -vector Multiset $\#k$ -SUM $\leq_{\lceil k/2\rceil}$ Multiset $\#k$ -SUM).

Lemma 16 ( $M$ -multiplicity $\#k$ -SUM $\leq_{\lceil k/2\rceil}$ $\#k$ -SUM).

Definition 20 (Verification of $d$ -dimensional Pareto Sum).

Definition 21 (Hausdorff Distance under $n$ Translations).

Lemma 23 (Hausdorff Distance under $n$ Translations is complete for $\mathsf{FOP}_{\mathbb{Z}}(\exists\forall\exists)$ ).

Lemma 24 (Verification of Pareto Sum is complete for $\mathsf{FOP}_{\mathbb{Z}}(\forall\forall\exists)$ ).

5.1 $\mathsf{FOP}_{\mathbb{Z}}(\forall\exists\exists)\to\mathsf{FOP}_{\mathbb{Z}}(% \exists\exists\exists)$

5.2 $\mathsf{FOP}_{\mathbb{Z}}(\exists\exists\exists)\to\mathsf{FOP}_{\mathbb{Z}}(% \forall\forall\exists)$

5.3 Completeness results for the class $\mathsf{FOP}_{\mathbb{Z}}^{k}$

6 The $3$ -SUM problem is complete for $\mathsf{FOP}_{\mathbb{Z}}$ formulas with Inequality Dimension at most 3

Lemma 27 (Disjoint decomposition of the union of cubes in $\mathbb{R}^{3}$ ).

Lemma 29 (Additive Sumset Approximation $\leq_{2}$ $3$ -SUM).