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 Patrascu (STOC 2010) who reduced 3SUM to an offline SetDisjointness problem. However, the reduction introduced by Patrascu 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 Patrascu'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.