Paper by Erik D. Demaine

Reference:

Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu, “Subquadratic Algorithms for 3SUM”, in Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005), Lecture Notes in Computer Science, volume 3608, Waterloo, Ontario, Canada, August 15–17, 2005, pages 409–421.

Abstract:

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² / max {w/lg² w, lg² n / (lg lg n)²}). In the circuit RAM with one nonstandard AC⁰ operation, we obtain O(n² (lg² w) / w²). In external memory, we achieve O(n² / (M B)), even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of O(n² (lg² M) / (M B)). 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.

Comments:

This paper is also available from SpringerLink.

Updates:

The proceedings version lists incorrect page numbers for reference [5].

Copyright:

The paper is \copyright Springer-Verlag.

Availability:

The paper is available in PostScript (330k), gzipped PostScript (149k), and PDF (193k).

See information on file formats.

[Google Scholar search]

Related papers:

3SUM_Algorithmica (Subquadratic Algorithms for 3SUM)