Solving k-SUM using few linear queries

DOI10.4230/LIPICS.ESA.2016.25zbMATH Open1397.68093arXiv1512.06678OpenAlexW2962888841MaRDI QIDQ4606294FDOQ4606294

Authors: Jean Cardinal, John Iacono, Aurélien Ooms 

Publication date: 2 March 2018

Abstract: The $k$-SUM problem is given $n$ input real numbers to determine whether any $k$ of them sum to zero. The problem is of tremendous importance in the emerging field of complexity theory within $P$, and it is in particular open whether it admits an algorithm of complexity $O(n^c)$ with $c<lceilfrack2ceil$. Inspired by an algorithm due to Meiser (1993), we show that there exist linear decision trees and algebraic computation trees of depth $O(n^{3}lo{g}^{3}n)$ solving $k$-SUM. Furthermore, we show that there exists a randomized algorithm that runs in $ildeO(n^{lceilfrack2ceil+8})$ time, and performs $O(n^{3}lo{g}^{3}n)$ linear queries on the input. Thus, we show that it is possible to have an algorithm with a runtime almost identical (up to the $+8$) to the best known algorithm but for the first time also with the number of queries on the input a polynomial that is independent of $k$. The $O(n^{3}lo{g}^{3}n)$ bound on the number of linear queries is also a tighter bound than any known algorithm solving $k$-SUM, even allowing unlimited total time outside of the queries. By simultaneously achieving few queries to the input without significantly sacrificing runtime vis-`{a}-vis known algorithms, we deepen the understanding of this canonical problem which is a cornerstone of complexity-within-$P$. We also consider a range of tradeoffs between the number of terms involved in the queries and the depth of the decision tree. In particular, we prove that there exist $o(n)$-linear decision trees of depth $o(n^4)$.

Full work available at URL: https://arxiv.org/abs/1512.06678

Recommendations

• A nearly quadratic bound for the decision tree complexity of \(k\)-SUM
• Near-optimal linear decision trees for \(k\)-SUM and related problems
• Near-optimal linear decision trees for k-SUM and related problems
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Deterministic time-space trade-offs for \(k\)-SUM

zbMATH Keywords

point location\(\varepsilon\)-netslinear decision trees\(k\)-SUM problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Data structures (68P05)

Cited In (13)

• Subquadratic algorithms for algebraic 3SUM
• Geometric pattern matching reduces to \(k\)-SUM
• Geometric Pattern Matching Reduces to k-SUM.
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Title not available (Why is that?)
• A nearly quadratic bound for the decision tree complexity of \(k\)-SUM
• Near-optimal linear decision trees for k-SUM and related problems
• Minimizing the sum of the \(k\) largest functions in linear time.
• Near-optimal linear decision trees for \(k\)-SUM and related problems
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Adversary lower bound for the \(k\)-sum problem
• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• On 3SUM-hard problems in the decision tree model

This page was built for publication: Solving \(k\)-SUM using few linear queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606294)