2026-07-20T14:45:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24510 2025-12-16T14:00:10Z ddc:004 open_access

(Multivariate) k-SUM as Barrier to Succinct Computation Gokaj, Geri Künnemann, Marvin Storandt, Sabine Truschel, Carina Fine-grained complexity theory sumsets additive combinatorics succinct inputs computational geometry How does the time complexity of a problem change when the input is given succinctly rather than explicitly? We study this question for several geometric problems defined on a set X of N points in ℤ^d. As succinct representation, we choose a sumset (or Minkowski sum) representation: Instead of receiving X explicitly, we are given sets A,B of n points that define X as A+B = {a+b∣ a ∈ A,b ∈ B}. We investigate the fine-grained complexity of this succinct version for several Õ(N)-time computable geometric primitives. Remarkably, we can tie their complexity tightly to the complexity of corresponding k-SUM problems. Specifically, we introduce as All-ints 3-SUM(n,n,k) the following multivariate, multi-output variant of 3-SUM: given sets A,B of size n and set C of size k, determine for all c ∈ C whether there are a ∈ A and b ∈ B with a+b = c. We obtain the following results: 1) Succinct closest L_∞-pair requires time N^{1-o(1)} under the 3-SUM hypothesis, while succinct furthest L_∞-pair can be solved in time Õ(n). 2) Succinct bichromatic closest L_∞-Pair requires time N^{1-o(1)} iff the 4-SUM hypothesis holds. 3) The following problems are fine-grained equivalent to All-ints 3-SUM(n,n,k): succinct skyline computation in 2D with output size k and succinct batched orthogonal range search with k given ranges. This establishes conditionally tight Õ(min{nk, N})-time algorithms for these problems. We obtain further connections with All-ints 3-SUM(n,n,k) for succinctly computing independent sets in unit interval graphs. Thus, (Multivariate) k-SUM problems precisely capture the barrier for enabling sumset-succinct computation for various geometric primitives. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Geri Gokaj and Marvin Künnemann and Sabine Storandt and Carina Truschel 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.42 urn:nbn:de:0030-drops-245101 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.42 eng https://creativecommons.org/licenses/by/4.0/legalcode