Speaker: Omer Gold (TAU) Title: Improved Subquadratic Algorithms for 3SUM Abstract: --------- Given a set of $n$ real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Gronlund and Pettie [FOCS'14], a simple $\Theta(n^2)$-time deterministic algorithm for this problem was conjectured to be optimal. The 3SUM problem and its variants are among the most fundamental problems in algorithm design. Although the 3SUM problem itself does not seem to have compelling practical implications, it has been of wide interest due to numerous problems that can be reduced from it. Thus, lower bounds on 3SUM imply lower bounds on dozens of other problems. Among them are fundamental problems in computational geometry, dynamic graph algorithms, triangle enumeration, and pattern matching data structures. Thus, any better understanding of the complexity of the 3SUM problem, might shed more light on the complexity of a wide class of problems in P. In this talk I will present: (i) The current best known deterministic algorithm for 3SUM, that runs in $O(n^2 (\log\log n)^2 / \log n )$ time. (ii) A randomized non-uniform (decision tree) algorithm for 3SUM that performs only $O(n^{3/2})$ expected comparisons. More generally, the randomized decision tree complexity of $k$-variate linear degeneracy testing is $O(n^{k/2})$, for any odd k>2. These bounds slightly improve the bounds obtained by Gronlund and Pettie [FOCS'14], giving a faster deterministic algorithm and new decision tree bound for this archetypal algorithmic problem. Joint work with Micha Sharir.