ACO The ACO Seminar (2017–2018)

Aug. 31, 3:30pm, Wean 8220
Shachar Lovett, UC San Diego
Linear decision trees for 3-SUM and a duality with active learning


The 3-SUM problem asks, given n real numbers x1,...,xn, whether there exist 3 of them that sum to zero. There is a trivial 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 would be very surprising), as it is a bottleneck for many problems in computational geometry and graph theory.

We show that in the linear decision tree model, 3-SUM has a near-linear 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. This improves upon previous work of Gronlund and Pettie (later improved by Gold and Sharir) which gives an O(n3/2) linear decision tree.

The same technique solves many combinatorial-geometric problems with near-optimal linear decision tree complexity. For example, for any k, we obtain a linear decision tree for k-SUM which makes O(kn polylog(n)) queries which are each 2k-sparse with {-1,0,1} coefficients. This matches a sparsity lower bound of Ailon and Chazelle. Other examples include sorting sumsets and subset sum.

The proof is based on a duality between the linear decision trees model and active learning. Specifically, it builds upon a new combinatorial notion called the "inference dimension".

Joint work with Daniel Kane and Shay Moran.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.

Back to the ACO home page