Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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

Duration: 30 minutes

Location: OAT S15/S16/S17

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login