CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar
Shachar Lovett
University of California, San Diego
Title: Linear decision trees for 3-SUM and a duality with active learning

Abstract: 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.

Date: Thursday, August 31, 2017
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Bukh
Note: Cookies and tea at 3:10 pm, Wean Hall 6220.