Solving $k$-SUM using few linear queries

Jean Cardinal, John Iacono, Aurélien Ooms

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 th…