Solving k-SUM using few linear queries

2015/12/21 by Cardinal, Jean, Iacono, John, Ooms, Aurélien · 1 citation
#Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1512.06678

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

Cited by

• Actively Learning Halfspaces without Synthetic Data

Related

• The Decision Tree Complexity for k-SUM is at most Nearly Quadratic
• Deterministic Time-Space Tradeoffs for k-SUM
• On the Hardness of Average-case k-SUM
• A novel and efficient algorithm to solve subset sum problem
• Space-Efficient Las Vegas Algorithms for K-SUM