Pith. sign in

REVIEW 4 major objections 4 minor 51 references

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

T0 review · 4 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that $k$-SUM is complete for the existential fragment of a logical class $\mathsf{FOP}_{\mathbb{Z}}$ of Presburger arithmetic sentences, and that Pareto Sum Verification together with Hausdorff distance under $n$…

desk verdict Genuinely new completeness framework for k-SUM over a logical class, but too many deferred proofs—especially Lemma 27—make acceptance conditional on the full version. read the letter →

arxiv 2502.04581 v1 pith:VIEACGJ5 submitted 2025-02-07 cs.CC cs.CGcs.LO

Geri Gokaj , Marvin Künnemann This is my paper · ORCID
classification cs.CCcs.CGcs.LO MSC 68Q1768Q2503B25
keywords fine-grainedcomplexityk-SUMhypothesisPresburgerarithmeticintegerlineardescriptiveParetosumverificationHausdorffdistanceundertranslationcompletenesstheorems
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks, in effect, how much of the difficulty of linear integer arithmetic is captured by the $k$-SUM problem. It defines a class $\mathsf{FOP}_{\mathbb{Z}}$ of model-checking problems: deciding prenex sentences in Presburger arithmetic over finite sets of integer points, with $k$ quantified variables ranging over the input sets. The main claims are that $k$-SUM is fine-grained complete for the $k$-existential-quantifier fragment, that $3$-SUM is complete for all $k$-quantifier sentences of inequality dimension at most $3$, and that the pair consisting of Pareto Sum Verification and Hausdorff distance under $n$ translations is complete for the whole class. If these claims hold, a subquadratic speed-up for $3$-SUM (or for either geometric problem) would translate into polynomial speed-ups for every sentence in the corresponding logical fragment, turning isolated algorithmic barriers into a single completeness story.

What carries the argument

The load-bearing mechanism is a collection of fine-grained reductions. The bit-level trick of Vassilevska Williams and Williams turns a conjunction of linear inequalities into a small number of conjunctions of linear equalities by guessing the most significant differing bit of each inequality; the vector $k$-SUM to $k$-SUM reduction of Abboud, Lewi, and Williams then collapses a conjunction of equalities into a single $k$-SUM instance. For counting versions, a heavy-light argument shows that multiset $\#k$-SUM is equivalent to $\#k$-SUM for odd $k$, and the recent equivalence between $3$-SUM and $\#3$-SUM supplies the counting hardness needed for quantifier changes. For the general-quantifier results, the paper proves a normal form (Lemma 22) reducing every $\mathsf{FOP}_{\mathbb{Z}}(Q_1 Q_2 \exists)$ formula to the syntactic form $Q_1 a_1 Q_2 a_2 \exists a_3 : a_1 + a_2 \le a_3$, uses the Additive Sumset Approximation problem to move between quantifier structures, and uses a decomposition of the union of $O(n)$ congruent cubes in $\mathbb{R}^3$ into $O(n)$ interior- and exterior-disjoint boxes (Lemma 27) to turn satisfiability of $\forall\exists$-formulas into a witness-counting condition against disjoint boxes.

What would settle it

Exhibit a concrete set of $n$ axis-aligned unit cubes in $\mathbb{R}^3$ whose union provably cannot be decomposed into $O(n)$ axis-aligned boxes with pairwise disjoint interiors and exteriors (for example, a construction requiring $\Omega(n \log n)$ boxes). Such a construction would refute Lemma 27 and invalidate Theorems 28 and 5 as stated; a simpler test is to compute the decomposition on large random cube sets and check whether the number of output boxes and the running time stay within $O(n)$ and $O(n \log^2 n)$, respectively.

Watch

Extended reading notes

Core claim

The paper's central discovery is a set of fine-grained completeness theorems that locate $k$-SUM and two geometric problems inside a logical class. Theorem 1 states that any problem of deciding an $\mathsf{FOP}_{\mathbb{Z}}$ formula with $k$ existential quantifiers reduces to $k$-SUM with only polylogarithmic overhead; Theorem 5 states that $3$-SUM is complete for all $\mathsf{FOP}_{\mathbb{Z}}$ formulas with $k$ quantifiers and inequality dimension at most $3$; Theorem 4 states that the pair (Pareto Sum Verification, Hausdorff distance under $n$ translations) is complete for all of $\mathsf{FOP}_{\mathbb{Z}}$, in the sense that a time $O(n^{2-\epsilon(d)})$ algorithm for both problems exists if and only if every $k$-quantifier sentence in $\mathsf{FOP}_{\mathbb{Z}}$ with $k \ge 3$ can be decided in time $O(n^{k-1-\epsilon_P})$. The paper also proves a counting version (Theorem 2 and Corollary 3), showing that counting witnesses for existential $\mathsf{FOP}_{\mathbb{Z}}$ formulas is no harder than counting $k$-SUM witnesses, and transfers the resulting hardness to the computation of Pareto sums (Theorem 7).

Load-bearing premise

The load-bearing assumption is Lemma 27, whose proof is deferred: the union of $n$ axis-aligned congruent cubes in $\mathbb{R}^3$ can be decomposed into $O(n)$ axis-aligned boxes with disjoint interiors and exteriors in $O(n \log^2 n)$ time; if that decomposition needs more boxes or more time, the counting mechanism behind $3$-SUM completeness for low-inequality-dimension formulas breaks down.

Editorial extensions

If this is right

  • A faster-than-$n^{\lceil k/2 \rceil}$ algorithm for $k$-SUM would speed up every problem in $\mathsf{FOP}_{\mathbb{Z}}(\exists^k)$ by a polynomial factor.
  • A faster-than-$n^2$ algorithm for $3$-SUM would imply polynomial speed-ups for all $\mathsf{FOP}_{\mathbb{Z}}$ formulas with $k$ quantifiers and inequality dimension at most $3$, regardless of quantifier structure.
  • A faster-than-$n^2$ algorithm for both Pareto Sum Verification and Hausdorff distance under $n$ translations would imply polynomial speed-ups for every $k$-quantifier sentence in $\mathsf{FOP}_{\mathbb{Z}}$.
  • A faster-than-$n^2$ algorithm for computing Pareto sums of sets with $\Theta(n)$ output size would refute the $3$-SUM hypothesis, and in dimension at least $2$ the same speed-up would speed up all $\mathsf{FOP}_{\mathbb{Z}}$ formulas not ending in $\exists\forall\exists$ or $\forall\exists\forall$.
  • A subquadratic algorithm for counting $3$-SUM witnesses would let us count witnesses of every existential $3$-quantifier $\mathsf{FOP}_{\mathbb{Z}}$ formula in subquadratic time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's invitation to treat Pareto Sum Verification as a high-dimensional generalization of $3$-SUM suggests that future hardness results could be organized around the dominance query 'does every sum $a+b$ lie below some $c$', making the verification problem a canonical representative of the whole class.
  • An immediate consequence of Theorem 4 that the authors leave implicit is that any exact algorithm for approximating Hausdorff distance under translation that improves on the $\tilde{O}(mn)$ baseline is constrained by every $\mathsf{FOP}_{\mathbb{Z}}$ lower bound, so future lower bounds for logic fragments can be read directly as lower bounds for geometric approximation.
  • Because the cube-decomposition lemma (Lemma 27) is deferred to the full version, the printed proof of Theorem 5 depends on an unverified geometric claim; a reader who distrusts the exterior-disjointness extension of the earlier interior-disjoint decomposition will want to check that step before relying on the result.
  • The barrier analysis suggests that proving $3$-SUM complete for all of $\mathsf{FOP}_{\mathbb{Z}}$ is equivalent to a tight reduction from the $3$-uniform hyperclique problem to $3$-SUM, so closing the remaining gap is plausibly as hard as relating two central fine-grained hypotheses.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper introduces a descriptive-complexity class FOP_Z of model-checking problems for prenex linear integer arithmetic formulas over finite integer sets, and proves fine-grained completeness results for k-SUM and two geometric problems. It claims that k-SUM is complete for the k-existential fragment (Theorem 1), that counting witnesses of existential FOP_Z formulas reduces to #k-SUM for odd k (Theorem 2, Corollary 3), that 3-SUM is complete for all k-quantifier FOP_Z formulas of inequality dimension at most 3 (Theorems 5 and 28), and that the pair consisting of Pareto Sum Verification and Hausdorff Distance under n Translations is complete for the entire class FOP^k_Z (Theorem 4). The paper also derives conditional lower bounds for Pareto sum computation. The proof strategy combines a bit-level reduction of inequalities to equalities, a heavy-light argument for multiset counting, reductions among quantifier structures via sumset approximation, and a geometric decomposition of the union of congruent cubes into disjoint boxes.

Significance. If the claims are correct, the paper gives a rare kind of fine-grained completeness: natural problems capturing a logically defined class over arithmetic. The existential-fragment completeness of k-SUM and the low-inequality-dimension completeness of 3-SUM would unify many existing reductions and provide a clean framework for conditional lower bounds. The problem-pair completeness of Pareto Sum Verification and Hausdorff Distance under n Translations is an ambitious and plausible generalization of 3-SUM. The paper is also careful to build on prior equivalences, such as the 3-SUM/#3-SUM equivalence of Chan et al. and Patrascu's convolutional 3-SUM equivalence, and I saw no circularity in the reduction structure. However, the manuscript as submitted is not self-contained: many load-bearing proofs, including the geometric Lemma 27 and the component lemmas of Theorem 4, are deferred to a full version, so the contribution is currently conditional on material the referee cannot check.

major comments (4)
  1. [§6, Lemma 27] Lemma 27 states that the union of n congruent axis-aligned cubes in R^3 can be decomposed into O(n) boxes with pairwise disjoint interiors and exteriors in O(n log^2 n) time, but the proof is deferred. This lemma is the counting mechanism in Theorem 28 and hence in Theorem 5: without exterior-disjointness, a point a'+b' could lie on the boundary of more than one box, and the witness count would no longer equal |A'|·|B'| (or, in the existential case, the number of b' witnessed by a given a'). A journal version must include the proof, or a precise citation establishing exactly this strengthening of the Chew et al. result [23].
  2. [§5.2–5.3, Theorem 10 and Lemmas 11–12] Theorem 4, the problem-pair completeness result for all of FOP^k_Z, rests on Lemmas 11 and 12, whose proofs are deferred, and on Theorem 10, whose proof is also deferred. These are not local technicalities: they are the only bridge from the syntactic normal forms of Lemma 22 to arbitrary quantifier prefixes of length k. As the manuscript stands, the paper's headline completeness claim cannot be verified from the text. The full proofs of Theorem 10, Lemma 11, and Lemma 12 must appear.
  3. [§3, Theorem 1 and Lemma 13] The foundational reduction showing that k-SUM is complete for FOP_Z(∃k) is only sketched. Lemma 13, which converts a conjunction of m linear inequalities into a unique disjunct of equality checks, is stated without proof, and the Vector k-SUM to k-SUM step is cited to [5] rather than proved. Since Theorem 1 underpins Theorem 2, Corollary 3, and the later quantifier-prefix arguments, the full reduction should be included.
  4. [§6, Theorem 5] Theorem 5 extends Theorem 28 from FOP^3_Z to FOP^k_Z with k≥3, but no proof of this extension is given; the text only says 'We can extend Theorem 28 to k-quantifiers by the following theorem.' The k-quantifier extension is a separate load-bearing claim, since it supplies the n^{k-1-ε} bounds advertised in the abstract and used in Theorem 7. A proof is needed to show how the counting/decomposition approach composes with arbitrary quantifier prefixes.
minor comments (4)
  1. [Abstract] The phrase 'faster-than-n^{⌈k/2⌉±o(1)}' is imprecise; the formal statements use O(n^{⌈k/2⌉−ε}) for some ε>0. Please rephrase for accuracy.
  2. [§7, Definition 33] Definition 33 has a typo: the output of Pareto Sum should be a set C⊆Z^d, not C⊆Z.
  3. [References] The reference list contains formatting errors, e.g., reference [46] spells the author as 'Puatracscu' instead of 'Patrascu'.
  4. [§5–§6] Several standard objects are used without definitions in the text, including All-ints 3-SUM, the Strong 3-SUM hypothesis, and the exact half-open boundary conventions in the boxes of Lemma 27; a journal version should make these precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main reductions are self-contained and rely on external prior results; deferred proofs and self-citations are not used to force the central conclusions.

full rationale

The paper's derivation chain consists of fine-grained reductions between syntactically defined classes (FOPZ fragments) and standard problems (k-SUM, 3-SUM, Pareto Sum Verification, Hausdorff distance under n Translations). No step defines a problem in terms of the class it is supposed to capture, and no fitted parameter is renamed as a prediction. Theorem 4's easy direction is simply that the two geometric problems belong to FOPZ^k, while the completeness direction is carried by independent reductions assembled in Lemmas 11 and 12. Theorem 5 and Theorem 28 reduce quantified formulas to counting witnesses in FOPZ(∃3), then invoke the external 3-SUM/#3-SUM equivalence of Chan et al. and reductions to 3-SUM; Lemma 27's deferred exterior-disjoint cube decomposition is a proof obligation and potential correctness risk, not a circularity, since it is an external geometric claim not equivalent to the target theorem. Self-citations to An et al. are used to state barriers and contextual hardness results, but these are not the load-bearing steps of Theorems 1, 4, or 5. No equation or theorem is shown to reduce to its own input by construction.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters or invented physical entities are present. The new objects are mathematical definitions, such as the class FOP_Z and the problem variants, which are standard practice in complexity theory. The main unproved ingredient is the geometric Lemma 27, listed as an ad hoc axiom because its proof is deferred and it is load-bearing for the low-inequality-dimension completeness result.

assumptions (7)
  • domain assumption Word-RAM model with O(log n)-bit words; input coordinates from {-U,...,U} with U <= n^c.
    Stated in Section 1.1; the reductions assume a polynomial-size universe for bit tricks and fine-grained time bounds.
  • domain assumption Fine-grained completeness notion: an O(T_A(n)^(1-epsilon)) algorithm for the complete problem A implies O(T_C(n)^(1-delta)) for every C in the class.
    Defined in Section 1.2; all completeness claims are relative to this definition.
  • standard math Subquadratic equivalence of 3-SUM and #3-SUM (Chan, Vassilevska Williams, Xu [22]).
    Used in Corollary 3 and Theorem 28 to reduce witness counting for FOP_Z(∃3) to 3-SUM.
  • standard math Subquadratic equivalence of 3-SUM and its convolutional version (Patrascu [46]).
    Invoked in the deferred proof of Theorem 10 for the Additive Sumset Approximation hardness direction.
  • standard math Bit-level trick converting a conjunction of linear inequalities to equality checks (Vassilevska Williams and Williams [52]).
    Used in Lemma 13 and Theorem 1 to reduce FOP_Z(∃k) to Vector k-SUM.
  • standard math Reduction from Vector k-SUM to k-SUM (Abboud, Lewi, Williams [5]).
    Used to complete the reduction in Theorem 1 and Lemma 15.
  • ad hoc to paper Lemma 27: the union of n axis-aligned congruent cubes in R^3 can be decomposed into O(n) pairwise interior- and exterior-disjoint boxes in O(n log^2 n) time.
    Proof deferred to the full version; this is the load-bearing geometric step in Theorem 28 and Theorem 5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic." pith.science (2026). https://pith.science/paper/VIEACGJ5

@misc{pith2026250204581,
  author       = {Pith},
  title        = {Pith review of: Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VIEACGJ5}},
  note         = {Machine review of arXiv:2502.04581}
}
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 \emph{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 \emph{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 \emph{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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 37 canonical work pages

  1. [23]

    Paul Chew, Dorit Dor, Alon Efrat, and Klara Kedem

    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. https://doi.org/10.1007/PL00009420 doi:10.1007/PL00009420

    work page doi:10.1007/pl00009420 1999

  2. [5]

    Losing weight by gaining edges

    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. https://doi.org/10.1007/978-3-662-44777-2...

    doi:10.1007/978-3-662-44777-2 2014

  3. [1]

    Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve

    Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin K \" u 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, 2...

    doi:10.1109/focs.2017.26 2017

  4. [2]

    Impossibility results for grammar-compressed linear algebra

    Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin K \" u 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 ...

    work page 2020

  5. [4]

    Exact weight subgraphs and the k-sum conjecture

    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--...

    doi:10.1007/978-3-642-39206-1 2013

  6. [6]

    Popular conjectures imply strong lower bounds for dynamic problems

    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. https://doi.org/10.1109/FOCS.2014.53 doi:10.1109/FOCS.2014.53

    doi:10.1109/focs.2014.53 2014

  7. [7]

    The fine-grained complexity of multi-dimensional ordering properties

    Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin K \" u nnemann, and Maria Paula Parga Nina. The fine-grained complexity of multi-dimensional ordering properties. Algorithmica , 84(11):3156--3191, 2022. URL: https://doi.org/10.1007/s00453-022-01014-x, https://doi.org/10.1007/S00453-022-01014-X doi:10.1007/S00453-022-01014-X

    work page doi:10.1007/s00453-022-01014-x 2022

  8. [8]

    State-based accelerations and bidirectional search for bi-objective multi-modal shortest paths

    Christian Artigues, Marie-Jos \'e Huguet, Fallou Gueye, Fr \'e d \'e 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

    work page 2013

Show all 51 references
  1. [9]

    Better approximations for tree sparsity in nearly-linear time

    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...

    2017 doi

  2. [10]

    How hard are n 2-hard problems? ACM SIGACT News , 25(2):83--85, 1994

    Stephen A Bloch, Jonathan F Buss, and Judy Goldsmith. How hard are n 2-hard problems? ACM SIGACT News , 25(2):83--85, 1994

    1994

  3. [11]

    Voronoi diagrams in higher dimensions under certain polyhedral distance functions

    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. https://doi.org/10.1007/PL00009366 doi:10.1007/PL00009366

    1998 doi

  4. [12]

    Fine-grained completeness for optimization in P

    Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin K \" u nnemann. Fine-grained completeness for optimization in P . In Mary Wootters and Laura Sanit \` a , editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM ...

    2021

  5. [13]

    A structural investigation of the approximability of polynomial-time problems

    Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin K \" u 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, Language...

    2022 doi

  6. [14]

    A fine-grained analogue of schaefer's theorem in P: dichotomy of exists \^ k-forall-quantified first-order graph properties

    Karl Bringmann, Nick Fischer, and Marvin K \" u 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, ...

    2019 doi

  7. [15]

    Sparse nonnegative convolution is equivalent to dense nonnegative convolution

    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, Ital...

    2021

  8. [16]

    Deterministic and las vegas algorithms for sparse nonnegative convolution

    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 / ...

    2022 doi

  9. [17]

    Fast n-fold boolean convolution via additive combinatorics

    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, Scotlan...

    2021 doi

  10. [18]

    Translating hausdorff is hard: Fine-grained lower bounds for hausdorff distance under translation

    Karl Bringmann and Andr \' e Nusser. Translating hausdorff is hard: Fine-grained lower bounds for hausdorff distance under translation. In Kevin Buchin and \' E ric Colin de Verdi \` e re, editors, 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2...

    2021 doi

  11. [19]

    Timothy M. Chan. Minimum l \_ \( \) 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...

    2023 doi

  12. [20]

    Chan and Moshe Lewenstein

    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 ...

    2015

  13. [21]

    Chan, Virginia Vassilevska Williams, and Yinzhan Xu

    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 The...

    2022

  14. [22]

    Chan, Virginia Vassilevska Williams, and Yinzhan Xu

    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...

    2023

  15. [24]

    Improvements on geometric pattern matching problems

    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

    1992

  16. [25]

    Paul Chew and Klara Kedem

    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 Not...

    1992 doi

  17. [26]

    Verifying candidate matches in sparse and wildcard matching

    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 \' e al, Qu \' e bec, Canada , pages 592--601. ACM , 2002. https://d...

    2002

  18. [27]

    On problems equivalent to (min, +)-convolution

    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. https://doi.org/10.1145/3293465 doi:10.1145/3293465

    2019 doi

  19. [28]

    Counting answers to existential questions

    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, 201...

    2019 doi

  20. [29]

    All non-trivial variants of 3-ldt are equivalent

    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 Theo...

    2020

  21. [30]

    A survey and annotated bibliography of multiobjective combinatorial optimization

    Matthias Ehrgott and Xavier Gandibleux. A survey and annotated bibliography of multiobjective combinatorial optimization. OR-spektrum , 22:425--460, 2000

    2000

  22. [31]

    New lower bounds for convex hull problems in odd dimensions

    Jeff Erickson. New lower bounds for convex hull problems in odd dimensions. SIAM J. Comput. , 28(4):1198--1214, 1999. https://doi.org/10.1137/S0097539797315410 doi:10.1137/S0097539797315410

    1999 doi

  23. [32]

    The effect of sparsity on k-dominating set and related first-order graph properties

    Nick Fischer, Marvin K \" u 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 ...

    2024 doi

  24. [33]

    Pareto sums of pareto sets: Lower bounds and algorithms

    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. URL: https://doi.org/10.48550/arXiv.2409.10232, https://arxiv.org/abs/2409.10232 arXiv:2409.10232 , https://do...

    2024 doi arXiv

  25. [34]

    Gabow, Jon Louis Bentley, and Robert Endre Tarjan

    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. ...

    1984

  26. [35]

    Overmars

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

    1995 doi

  27. [36]

    Completeness for first-order properties on sparse structures with algorithmic applications

    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. https://doi.org/10.1145/3196275 doi:10.1145/3196275

    2019 doi

  28. [37]

    Pareto sums of pareto sets

    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 ...

    2023 doi

  29. [38]

    Huttenlocher and Klara Kedem

    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. ht...

    1990

  30. [39]

    3sum, 3xor, triangles

    Zahra Jafargholi and Emanuele Viola. 3sum, 3xor, triangles. Algorithmica , 74(1):326--343, 2016. URL: https://doi.org/10.1007/s00453-014-9946-9, https://doi.org/10.1007/S00453-014-9946-9 doi:10.1007/S00453-014-9946-9

    2016 doi

  31. [40]

    Higher lower bounds from the 3sum conjecture

    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. ...

    2016 doi

  32. [41]

    A tight (non-combinatorial) conditional lower bound for klee's measure problem in 3d

    Marvin K \" u 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. https://doi.o...

    2022

  33. [42]

    Wang, and R

    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, Languag...

    2016 doi

  34. [43]

    Ryan Williams

    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, Janua...

    2018 doi

  35. [44]

    Variable and large neighborhood search to solve the multiobjective set covering problem

    Thibaut Lust and Daniel Tuyttens. Variable and large neighborhood search to solve the multiobjective set covering problem. Journal of Heuristics , 20:165--188, 2014

    2014

  36. [45]

    Fine-grained complexity and algorithm engineering of geometric similarity measures

    Andr \' e Nusser. Fine-grained complexity and algorithm engineering of geometric similarity measures . PhD thesis, Saarland University, Saarbr \" u cken, Germany, 2021. URL: https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/33904

    2021

  37. [46]

    Towards polynomial lower bounds for dynamic problems

    Mihai P u a tra c s cu. 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. https://doi.org/10....

    2010

  38. [47]

    Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions

    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

    2019

  39. [48]

    Shape matching in higher dimensions

    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

    2003

  40. [49]

    Faster decision of first-order graph properties

    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 Scienc...

    2014

  41. [50]

    On some fine-grained questions in algorithms and complexity

    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

    2018

  42. [51]

    Subcubic equivalences between path, matrix and triangle problems

    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

  43. [52]

    Finding, minimizing, and counting weighted subgraphs

    Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. , 42(3):831--854, 2013. https://doi.org/10.1137/09076619X doi:10.1137/09076619X

    2013 doi

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.