Solving k-SUM Using Few Linear Queries
Jean Cardinal, John Iacono, Aurélien Ooms · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
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