2005 Gödel Prize

The 2005 Gödel Prize for outstanding papers in the area of theoretical computer science is awarded to Noga Alon, Yossi Matias and Mario Szegedy for their paper: Manindra Agrawal, Neeraj Kayal, and Nitin Saxena for their paper:

The space complexity of approximating the frequency moments. Journal of Computer and System Sciences 58 (1999), 137-147
First presented at the 28th ACM Symposium on Theory of Computing, 1996.

This concise work laid the foundations of the analysis of data streams using limited memory. It demonstrated the design of small randomized linear projections, subsequently referred to as "sketches," that summarize large amounts of data and allow quantities of interest to be approximated to user-specified precision.

The technical contributions include the unexpected result that the second frequency moment of a stream of values can be approximated using logarithmic space. The authors also show that no analogous result holds for higher frequency moments.

Due to the simplicity, elegance, and wide applicability of its techniques, the paper set the pattern for a rapidly growing body of work, both theoretical and applied, and created the now burgeoning fields of streaming and sketching algorithms.

The areas of practical application include query planning and processing in databases and the design of small synopses to monitor vast quantities of data generated in networks. The ideas have since enabled effective, one-pass algorithms for numerous data-streaming problems, including relational join queries, top-k frequency estimation, histogram and wavelet construction, and correlating XML data streams.

The paper demonstrates that the theory of computing continues to be a powerful source of mathematical ideas with immediate and profound impact on the practice in other communities such as databases and networking.

Award Committee