Development of efficient randomized tests of primality
Gary Miller, Michael Rabin, Robert Solovay, Volker Strassen
For the development of efficient randomized tests of primality, enabling the practical realization of public key cryptography and demonstrating the power of randomized algorithms.
ABOUT THIS AWARD
The 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 Computational Theory (SIGACT), Design Automaton (SIGDA), Management of Data (SIGMOD), and Programming Languages (SIGPLAN), the ACM SIG Projects Fund, and individual contributions.
Robert D. Blumofe and Charles E. Leiserson, recipients of the 2013 Paris Kanellakis Theory and Practice Award
Robert D. Blumofe and Charles E. Leiserson, recipients of the Paris Kanellakis Theory and Practice Award for contributions to robust parallel and distributed computing. They developed provably efficient randomized “work-stealing” scheduling algorithms, and Cilk, a small set of linguistic primitives (the simplest elements in a programming language) for programming multithreaded computations. Their conceptual framework for work stealing is ubiquitous on scores of millions of multicore platforms and underpins many parallel-programming platforms. Cilk simplifies multiprocessor programming and guarantees mathematically that multithreaded programs with sufficient parallelism run with near-perfect speed. Blumofe is an Executive Vice President at Akamai Technologies, where he is responsible for the Platform Division, which includes the core distributed systems and network technology that underlie all of Akamai’s products and services. Leiserson, Professor of Computer Science and Engineering at the Massachusetts Institute of Technology, is co-author of Introduction to Algorithms, won the ACM Doctoral Dissertation Award, and is an ACM Fellow.
ACM will present the 2013 ACM Awards at its annual Awards Banquet on June 21 in San Francisco, CA.
Andrei Broder, Moses Charikar, Piotr Indyk named recipients of the 2012 Paris Kanellakis Theory and Practice Award
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.
