## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, May 18, 2017, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Luis Barba

## Subquadratic Algorithms for Algebraic Generalizations of 3SUM

The 3SUM problem asks if a given $n$-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. Gronlund and Pettie recently showed the existence of subquadratic algorithms for 3SUM. We streamline their results and extend their scope to 3POL. Using tools from computational geometry we prove that there exist algebraic-computation trees of depth $O(n^{\frac{12}{7}+\varepsilon})$ that solve 3POL, and that 3POL can be solved in $O(n^2 (\log \log n)^\frac{3}{2} / (\log n)^\frac{1}{2})$time in the real-RAM model. This is joint work with J. Cardinal, J. Iacono, S. Langerman, A. Ooms and N. Salomon.

Information for students and suggested topics for student talks