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 x,...,_{1}x, whether there exist _{n}3 of them that sum to zero. There is a trivial 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 would be very surprising), as it is a bottleneck for many problems in computational geometry and graph theory.^{2}We show that in the linear decision tree model, 3-SUM has a near-linear 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 *comparison queries* of the form "x_{i}+x_{j}+x_{k}>x_{a}+x_{b}+x_{c} ?". 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(n^{3/2}) linear decision tree.The same technique solves many combinatorial-geometric problems with near-optimal linear decision tree complexity. For example, for any 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. https://arxiv.org/abs/1705.01720 |