Aug. 31, 3:30pm, Wean 8220

Shachar Lovett, UC San Diego

Linear decision trees for 3-SUM and a duality with active learning

Shachar Lovett, UC San Diego

Linear decision trees for 3-SUM and a duality with active learning

Abstract:

The 3-SUM problem asks, given *n* real numbers *x _{1}*,...,

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 *a _{i} x_{i}*>

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. https://arxiv.org/abs/1705.01720

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