Higher lower bounds from the 3SUM conjecture – University of Copenhagen

Higher lower bounds from the 3SUM conjecture

EADS talk by Tsvi Kopelowitz, Postdoctoral Fellow at University of Michigan

Abstract

The 3SUM hardness conjecture has proven to be a valuable and popular tool for proving conditional lower bounds on the complexities of dynamic data structures and graph problems. This line of work was initiated by Patrascu [STOC 2010] and has received a lot of recent attention. Most of these lower bounds are based on reductions from 3SUM to a special set intersection problem introduced by Patrascu, which we call Patrascu's Problem. However, the framework introduced by Patrascu that reduces 3SUM to Patrascu's Problem suffers from some limitations, which in turn produce polynomial gaps between the achievable lower bounds via this framework and the known upper bounds.

We address these issues by providing a tighter and more versatile framework for proving 3SUM lower bounds via a new reduction to Patrascu's Problem. Furthermore, our framework does not become weaker if 3SUM can be solved in truly subquadratic time, and provides some immediate higher conditional lower bounds for several problems, including for set intersection data-structures. For some problems, the new higher lower bounds meet known upper bounds, giving evidence to the optimality of such algorithms.

During the talk, we will discuss this new framework, and show some new (optimal) lower bounds conditioned on the 3SUM hardness conjecture. In particular, we will demonstrate how some old and new triangle listing algorithms are optimal for any graph density, and, time permitting, prove a conditional lower bound for incremental Maximum Cardinality Matching which introduces new techniques for obtaining amortized lower bounds.

Short bio

I am currently a Postdoctoral Fellow in the Department of Electrical Engineering and Computer Science in University of Michigan, hosted by Seth Pettie. Before that I was a Postdoctoral Fellow in the Faculty of Mathematics and Computer Science in The Weizmann Institute of Science, hosted by Robert Krauthgamer. I completed my PhD in the Computer Science Department of Bar Ilan University, under the supervision of Moshe Lewenstein.