Paper by Erik D. Demaine

Reference:

Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu, “Subquadratic Algorithms for 3SUM”, Algorithmica, volume 50, number 4, April 2008, pages 584–596. Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005.

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.

Availability:

The paper is available in PostScript (331k), gzipped PostScript (146k), and PDF (196k).

See information on file formats.

[Google Scholar search]

Related papers:

3SUM_WADS2005 (Subquadratic Algorithms for 3SUM)