Shachar Lovett (Theory Seminar)

Shachar Lovett (UCSD)
Monday, May 15, 2017, 2:00pm


Title: The decision tree complexity of k-SUM is near-linear


The 3-SUM problem asks, given n real numbers x1,...,xn, whether there exist 3 of them that sum to zero. There is a simple algorithm that solves it in O(n2) time, and the best algorithm to date only improves upon it in logarithmic terms. A significantly better algorithm is believed to be impossible (or at least very surprising).

We show that in the linear decision tree model, 3-SUM has an O(n polylog(n)) algorithm. A linear decision tree is an adaptive algorithm which makes linear queries of the form "sum ai xi>0 ?" to the input x, and at the end decides whether a 3-SUM exists.

Moreover, the type of queries we use are only label queries of the form "xi+xj+xk>0 ?" or comparison queries of the form "xi+xj+xk>xa+xb+xc ?". Thus, the queries are all 6-sparse linear queries with {-1,0,1} coefficients. More generally, for any constant k, we get a linear decision tree for k-SUM which makes O(n polylog(n)) queries which are each 2k-sparse with {-1,0,1} coefficients.

The proof is based on a connection between the linear decision trees model and active learning, in particular the recently introduced notion of "inference dimension".

(Joint work with Daniel Kane and Shay Moran.)

Theory Seminar