About ACM Paris Kanellakis Theory and Practice Award

Michael Burrows, Google; Paolo Ferragina, University of Pisa; and Giovanni Manzini, University of Pisa, receive the ACM Paris Kanellakis Theory and Practice Award for inventing the BW-transform and the FM-index that opened and influenced the field of Compressed Data Structures with fundamental impact on Data Compression and Computational Biology.

In 1994, Michael Burrows and his late coauthor David Wheeler published their paper describing revolutionary data compression algorithm based on a reversible transformation of the input. This transformation, which became known as the “Burrows-Wheeler Transform” (BWT), was used as the core of the compressor bzip2. bzip2 achieved compression performance superior to the standard of the time.

A few years later, Paolo Ferragina and Giovanni Manzini showed that, by orchestrating the BWT with a new set of mathematical techniques and algorithmic tools, it became possible to build a “compressed index,” later called the FM-index. Before the FM-index, it seemed unavoidable to incur a significant space penalty for achieving efficient queries. With the FM-index, Ferragina and Manzini were able to disprove this common belief. In addition to being a theoretical breakthrough, the simplicity and effectiveness of the FM-index has made it a premier indexing choice for software tools working on large collections of unstructured data, with the most impressive applications in the field of DNA alignment and Computational Biology in general.

The introduction of the BW Transform by Burrows and Wheeler, and then the development of the FM-index by Ferragina and Manzini, have had a profound impact on the theory of algorithms and data structures with fundamental advancements—first and foremost to Data Compression and Computational Biology, but also to a number of applications in many other areas, including Databases and Information Retrieval at large.

Avrim Blum, Toyota Technological Institute at Chicago; Irit Dinur, Weizmann Institute; Cynthia Dwork, Harvard University; Frank McSherry, Materialize Inc.; Kobbi Nissim, Georgetown University; and Adam Davison Smith, Boston University, receive the ACM Paris Kanellakis Theory and Practice Award for their fundamental contributions to the development of differential privacy.

Differential privacy is a definition and framework for reasoning about privacy in statistical databases. While the privacy of individuals contributing to a dataset has been a long-standing concern, prior to the Kanellakis recipients’ work, computer scientists only knew how to mitigate several specific privacy attacks via a disparate set of techniques. The foundation for differential privacy emerged in the early 2000’s from several key papers. At the ACM Symposium on the Principles of Database Systems (PODS 2003) Dinur and Nissim presented a paper which showed that any technique that allows reasonably accurate answers to a large number of queries is inherently non-private.

Later, a sequence of papers by Dwork and Nissim at the International Conference on Cryptology (Crypto 2004); as well as Blum, Dwork, McSherry, and Nissim at the ACM Symposium on the Principles of Database Systems (PODS 2005); and Dwork, McSherry, Nissim, and Smith at the Theory of Cryptology Conference (TCC 2006) further defined and studied the notion of differential privacy.

These separate but related papers formed a definition of differential privacy which captures the kind of privacy needed in statistical settings, where individual information must be protected while still allowing for discovery of common trends. These fundamental works created a vibrant and multidisciplinary area of research, leading to practical deployments of Differential Privacy in industry and by the U.S. Census Bureau, among other applications.

The authors also showed that their definition includes post-processing and composition properties that facilitate design, analysis, and applications of differentially private algorithms. The Laplace and the Gaussian noise mechanisms, which show differentially private analogs of statistical query learning algorithms, also grew out of the Kanellakis recipients’ work on differential privacy.

Yossi Azar, Tel Aviv University; Andrei Broder, Google Research; Anna Karlin, University of Washington; Michael Mitzenmacher, Harvard University; and Eli Upfal, Brown University, receive the ACM Paris Kanellakis Theory and Practice Award for the discovery and analysis of balanced allocations, known as the power of two choices, and their extensive applications to practice.

Azar, Broder, Karlin, Mitzenmacher and Upfal introduced the Balanced Allocations framework, also known as the power of two choices paradigm, an elegant theoretical work that had a widespread practical impact.

When n balls are thrown into n bins chosen uniformly at random, it is known that with high probability, the maximum load on any bin is bounded by (lg n/lg lg n) (1+o(1)). Azar, Broder, Karlin, and Upfal (STOC 1994) proved that adding a little bit of choice makes a big difference. When throwing each ball, instead of choosing one bin at random, choose two bins at random, and then place the ball in the bin with the lesser load. This minor change brings on an exponential improvement; now with high probability, the maximal load in any bin is bounded by (lg lg n/lg 2)+O(1).

In the same work, they have shown that, if each ball has d choices, then the maximum load drops with high probability to (ln ln n/ ln d)+O(1). These results were greatly extended by Mitzenmacher in his 1996 PhD dissertation, where he removed the sequential setting, and developed a framework for using the power of two choices in queueing systems.

Since bins and balls are the basic model for analyzing data structures, such as hashing or processes like load balancing of jobs in servers, it is not surprising that the power of two choices that requires only a local decision rather than global coordination has led to a wide range of practical applications. These include i-Google's web index, Akamai’s overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox, which are all based on variants of the power of two choices paradigm. There are many other software systems that use balanced allocations as an important ingredient.

The Balanced Allocations paper and the follow-up work on the power of two choices are elegant theoretical results, and their content had, and will surely continue to have, a demonstrable effect on the practice of computing.

ACM has named Noga Alon of Princeton University and Tel Aviv University; Phillip Gibbons of Carnegie Mellon University; Yossi Matias of Google and Tel Aviv University; and Mario Szegedy of Rutgers University recipients of the ACM Paris Kanellakis Theory and Practice Award for seminal work on the foundations of streaming algorithms and their application to large-scale data analytics.

Alon, Gibbons, Matias and Szegedy pioneered a framework for algorithmic treatment of streaming massive datasets. Today, their sketching and streaming algorithms remain the core approach for streaming big data and constitute an entire subarea of the field of algorithms. Additionally, the concepts of sketches and synopses that they introduced are now routinely used in a variety of data analysis tasks in databases, network monitoring, usage analytics in internet products, natural language processing and machine learning.

In their seminal paper, “The Space Complexity of Approximating the Frequency Moments,” Alon, Matias and Szegedy laid the foundations of the analysis of data streams using limited memory. Follow-up papers, including “Tracking Join and Self-join Sizes in Limited Storage,” by Alon, Gibbons, Matias, and Szegedy, and “New Sampling-Based Summary Statistics for Improving Approximate Query Answers,” by Gibbons and Matias, expanded on the idea of data synopses and were instrumental in the development of the burgeoning fields of streaming and sketching algorithms. This work has been applied to query planning and processing in databases and the design of small synopses to monitor vast quantities of data generated in networks.

Pavel Pevzner, a professor at the University of California San Diego, receives the ACM Paris Kanellakis Theory and Practice Award for pioneering contributions to the theory, design and implementation of algorithms for string reconstruction and to their applications in the assembly of genomes.

Pevzner’s research interests span the field of computational biology, and his work has been guided by tailoring algorithmic ideas to biological problems. The life sciences have been transformed by the ability to rapidly sequence and assemble genomes for organisms from existing and extant species and use these assembled genomes to answer fundamental and applied questions in biology, medicine and other sciences. Pevzner has made fundamental contributions to the theoretical study of string algorithms and to their application to scalable reconstruction of genomes and other biological sequences such as antibodies and antibiotics. Pevzner’s algorithms underlie almost all sequence assemblers used today and were used to reconstruct the vast majority of genomic sequences available in databases.

The ACM Paris Kanellakis Theory and Practice Award honors specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing. This award is accompanied by a prize of $10,000 and is endowed by contributions from the Kanellakis family, with additional financial support provided by ACM's Special Interest Groups on Algorithms and Computation Theory (SIGACT), Design Automation (SIGDA), Management of Data (SIGMOD), and Programming Languages (SIGPLAN), the ACM SIG Projects Fund, and individual contributions.

Scott Shenker was honored for pioneering contributions to fair queueing in packet-switching networks, which had a major impact on modern practice in computer communication. Shenker’s work was fundamental to helping the internet grow from a tool used by a small community of researchers, to a staple of daily life that is used by billions of people. Since the internet was introduced, demand has grown for the ability of computer networks to transmit voice and data simultaneously. Traditionally, this was a challenge, as early networks were not designed to offer integrated services. Shenker was the first to develop the first practical fair queueing algorithm for packet-switching networks, which provided equitable access to transmission bandwidth for different grades of service quality. Many of the commercial routers that make up the internet today use Shenker’s algorithms.

Shenker also developed a mathematical tool for rigorous network research, and introduced ideas for implementing “guaranteed” real-time services such as voice, video streaming and multicasts. Recently, Shenker has been involved in positing how to redesign the internet from the ground up. Software-defined networking (SDN) and software-defined internet architecture (SDIA) are key ideas he developed as part of these inquiries. Researchers consider SDN and SDIA invaluable concepts for mapping out how to most effectively maintain and expand the internet in the coming years.

The ACM Paris Kanellakis Theory and Practice Award honors specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing. This award is accompanied by a prize of $10,000 and is endowed by contributions from the Kanellakis family, with additional financial support provided by ACM's Special Interest Groups on Algorithms and Computation Theory (SIGACT), Design Automation (SIGDA), Management of Data (SIGMOD), and Programming Languages (SIGPLAN), the ACM SIG Projects Fund, and individual contributions.

Amos Fiat and Moni Naor were honored for the development of broadcast encryption and traitor tracing systems. Sending broadcast transmissions that only paid subscribers have access to is one of the most important parts of a pay TV system. A traditional challenge of sending encrypted keys to subscribers has been that the pool of subscribers is constantly changing, as are the specific package of channels each customer may be subscribing to at any time. Traditional approaches to Broadcast Encryption would require TV providers to send either very long transmissions or for subscribers to store an inordinate number of cryptographic keys. In 1993, the Israeli team of Amos Fiat and Moni Naor published their landmark paper Broadcast Encryption, which proposed a system of broadcast encryption that was efficient, both in terms of the length of the transmissions the provider sends, and the number of keys a subscriber would need to store. Fiat and Naor’s work is widely regarded as laying the foundation of the broadcast encryption field. Their original ideas are now used by cable television and satellite radio providers to ensure that only paying subscribers can decrypt a broadcast. A form of broadcast encryption is also the standard key management system that is used to protect against the unauthorized copying of Blu-ray discs.

Building on this work, Fiat (Tel Aviv University) and Naor (Weizmann Institute of Science) collaborated with Benny Chor to invent traitor tracing. Traitor tracing enables legal parties who leak their keys to unauthorized parties to be tracked down and identified. Traitor tracing has been an important tool in the war against piracy.

The ACM Paris Kanellakis Theory and Practice Award honors specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing. This award is accompanied by a prize of $10,000 and is endowed by contributions from the Kanellakis family, with additional financial support provided by ACM's Special Interest Groups on Algorithms and Computation Theory (SIGACT), Design Automation (SIGDA), Management of Data (SIGMOD), and Programming Languages (SIGPLAN), the ACM SIG Projects Fund, and individual contributions.

ACM announced the recipients of four prestigious technical awards:  ACM Grace Murray Hopper Award, ACM Paris Kanellakis Theory and Practice Award, ACM-AAAI Allen Newell Award, and ACM Software System Award. These innovators were selected by their peers for making significant contributions that enable the computing field to solve real-world challenges. The awards reflect achievements in cryptography, network coding systems, computer-human interaction, and software systems. The 2015 recipients will be formally honored at the ACM Awards Banquet on June 11 in San Francisco.

Michael Luby, recipient of the ACM Paris Kanellakis Theory and Practice Award for groundbreaking contributions to erasure correcting codes, which are essential for improving the quality of video transmission over the Internet. An important aspect of coding theory is to ensure that it is possible to recover data at a receiver transmitted from a sender, despite the fact that errors, often occurring naturally from “noise” on a channel, can impair the transmission. In coding theory, Luby made several theoretical contributions —including, but not limited to, Tornado Codes, Fountain Codes, and LT Codes — that have led to major advances in the reliable transmission and recoverability of data across mobile, broadcast and satellite channels. His work on erasure correcting codes has had an especially significant impact on the ability to stream videos, including mobile broadcast TV channels. Luby’s contributions have been applied to military technology as well as consumer devices in both wired and wireless networks. Luby is a vice president of technology at Qualcomm Technologies, Inc., a subsidiary of Qualcomm Incorporated, and an ACM Fellow.

James Demmel is the recipient of the Paris Kanellakis Theory and Practice Award for his work on numerical linear algebra libraries, including LAPACK (Linear Algebra Package), a standard software library that forms part of the standard mathematical libraries for many vendors. The software and standards Demmel developed enable users to transition their computer programs to new high-performance computers without resorting to basic building blocks. His accomplishments range from creation of algorithms with rigorous mathematical foundations to hands-on development of high-quality, widely available software. Demmel is a professor of Computer Science and of Mathematics at UC Berkeley and an ACM Fellow.

Press Release

Broder, Charikar, and Indyk were recognized for their work on algorithms that allow for quickly finding similar entries in large databases, known as locality-sensitive hashing (LSH), These algorithms can drastically reduce the computational time needed for retrieving similar items, at the cost of a small probability of failing to find the absolute closest match.  LSH has impacted fields as diverse as computer vision, databases, information retrieval, data mining, machine learning, and signal processing.

Andrei Broder introduced specific locality-sensitive min-hash functions, used to estimate the similarity of data sets and identify near-duplicate documents.  He is a Google Distinguished Scientist.  

Piotr Indyk, with the late Rajeev Motwani, extended LSH functions to a wider range of distance functions, and applied them to design efficient approximate nearest neighbor algorithms. Indyk is a professor at MIT's Computer Science and Artificial Intelligence Lab.  

Moses Charikar introduced sim-hash functions for angular distances. He is a professor of Computer Science at Princeton University.