The 2005 Gödel Prize
Posted by Sachin Garg on 16th September 2005 | Permanent Link
The 2005 Gödel Prize is awarded to Noga Alon, Yossi Matias and Mario Szegedy for their paper “The space complexity of approximating the frequency moments”
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.
A leading innovator in information and data management technologies, Dr. Matias has authored numerous research papers and holds over 20 patents on diverse technologies relating to data and information management, systems, and algorithms. Dr. Matias is on leave from his faculty position at Tel Aviv University and, in addition to his position at HyperRoll’s CTO, is a visiting professor at Stanford University. His research involves algorithms for data streams and data synopses for massive data sets, parallel computation, data compression, and Internet technologies.
The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery (ACM-SIGACT). This award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and the ACM Symposium on Theory of Computing (STOC). The Prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before Neumann’s death, in what has become the famous “P versus NP” question.
The Prize includes an award of $5000.