Subquadratic Algorithms for 3SUM

摘要

We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of O(n~2/max{w/(lg~2 w), (lg~2 n)/ ((lg lg n))~2}). In the circuit RAM with one nonstandard AC~0 operation, we obtain O(n~2/((w~2) /(lg~2w))). In external memory, we achieve O(n~2/(M B)), even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of O(n~2/((MB)/(lg~2 M))). In all cases, our speedup is almost quadratic in the parallelism the model can afford, which may be the best possible. Our algorithms are Las Vegas randomized; time bounds hold in expectation, and in most cases, with high probability.