3SUM in Preprocessed Universes: Faster and Simpler

Shashwat Kasliwal, Adam Polak, Pratyush Sharma

We revisit the 3SUM problem in the \emph{preprocessed universes} setting. We present an algorithm that, given three sets $A$, $B$, $C$ of $n$ integers, preprocesses them in quadrat…