Shachar Lovett (UCSD)

Monday, May 15, 2017, 2:00pm

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

Abstract:

The *3-SUM* problem asks, given n real numbers *x _{1},...,x_{n}*, whether there exist 3 of them that sum to zero. There is a simple algorithm that solves it in

*O(n*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).

^{2})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 a _{i} x_{i}>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 "x

_{i}+x

_{j}+x

_{k}>0 ?" or

__of the form__

*comparison queries**"x*. Thus, the queries are all 6-sparse linear queries with

_{i}+x_{j}+x_{k}>x_{a}+x_{b}+x_{c}?"*{-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.)