- Daniel A. Spielman, Shang-Hua Teng:
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3): 385-463 (2004) - Robert C. Steinke, Gary J. Nutt:
A unified theory of shared memory consistency. J. ACM 51(5): 800-849 (2004) - Mikkel Thorup:
Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6): 993-1024 (2004)