ICS Theory Group

Winter 2016: Theory Seminar
ICS, Room 243, 1:00pm


February 19, 2016:

Higher Lower Bounds from the 3SUM Conjecture

Tsvi Kopelowitz

Abstract:

The 3SUM Conjecture has proven to be a valuable tool for proving conditional lower bounds on dynamic data structures and graph problems. This line of work was initiated by Pătraşcu (STOC 2010) who reduced 3SUM to an offline SetDisjointness problem. However, the reduction introduced by Pătraşcu suffers from several inefficiencies, making it difficult to obtain tight conditional lower bounds from the 3SUM conjecture.

In this talk I'll discuss the deficiencies of Pătraşcu's framework, then give new and efficient reductions from 3SUM to offline SetDisjointness and offline SetIntersection (the reporting version of SetDisjointness) which leads to polynomially higher lower bounds on several problems.

(Joint work with Seth Pettie and Ely Porat from SODA 2016.)

About the speaker:

Tsvi Kopelowitz is a postdoctoral fellow in the Department of Electrical Engineering and Computer Science at the University of Michigan. He earned his Ph.D. from Bar-Ilan University in 2011, and has also been a postdoctoral fellow at the Weizmann Institute of Science.