TY - GEN

T1 - Solving k-SUM using few linear queries

AU - Cardinal, Jean

AU - Iacono, John

AU - Ooms, Aurélien

N1 - Funding Information:
Supported by the "Action de Recherche Concertée" (ARC) COPHYMA, convention number 4.110.H.000023. Research partially completed while on on sabbatical at the Algorithms Research Group of the Département d'Informatique at the Université Libre de Bruxelles with support from a Fulbright Research Fellowship, the Fonds de la Recherche Scientifique - FNRS, and NSF grants CNS-1229185, CCF-1319648, and CCF-1533564. Supported by the Fund for Research Training in Industry and Agriculture (FRIA).
Publisher Copyright:
© Jean Cardinal, John Iacono, and Aurélien Ooms.

PY - 2016/8/1

Y1 - 2016/8/1

N2 - 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(nc) with c < ⌊k/2⌋. Inspired by an algorithm due to Meiser (1993), we show that there exist linear decision trees and algebraic computation trees of depth O(n3 log2 n) solving k-SUM. Furthermore, we show that there exists a randomized algorithm that runs in Õ(n⌊k/2⌋+8) time, and performs O(n3 log2 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(n3 log2 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-à-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 Õ(n3) for the k-SUM problem.

AB - 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(nc) with c < ⌊k/2⌋. Inspired by an algorithm due to Meiser (1993), we show that there exist linear decision trees and algebraic computation trees of depth O(n3 log2 n) solving k-SUM. Furthermore, we show that there exists a randomized algorithm that runs in Õ(n⌊k/2⌋+8) time, and performs O(n3 log2 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(n3 log2 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-à-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 Õ(n3) for the k-SUM problem.

KW - H-SUM problem

KW - Linear decision trees

KW - Point location

KW - ϵ-nets

UR - http://www.scopus.com/inward/record.url?scp=85012977552&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85012977552&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2016.25

DO - 10.4230/LIPIcs.ESA.2016.25

M3 - Conference contribution

AN - SCOPUS:85012977552

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 24th Annual European Symposium on Algorithms, ESA 2016

A2 - Zaroliagis, Christos

A2 - Sankowski, Piotr

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 24th Annual European Symposium on Algorithms, ESA 2016

Y2 - 22 August 2016 through 24 August 2016

ER -