The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery (ACM) to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". [1] It was instituted in 1996, in memory of Paris C. Kanellakis, a computer scientist who died with his immediate family in an airplane crash in South America in 1995 (American Airlines Flight 965). [2] The award is accompanied by a prize of $10,000 and is endowed by contributions from Kanellakis's parents, with additional financial support provided by four ACM Special Interest Groups (SIGACT, SIGDA, SIGMOD, and SIGPLAN), the ACM SIG Projects Fund, [3] and individual contributions. [1]
Year | Winners | Citation |
---|---|---|
1996 | Leonard Adleman, Whitfield Diffie, Martin Hellman, Ralph Merkle, Ronald Rivest, and Adi Shamir | For "the conception and first effective realization of public-key cryptography". [4] |
1997 | Abraham Lempel and Jacob Ziv | For their pioneering work in data compression, leading to their LZ algorithm which "yields the best compression rate achievable by finite-state encoders" and "can be found in virtually every modern computer". [5] |
1998 | Randal Bryant, Edmund M. Clarke, E. Allen Emerson, and Kenneth L. McMillan | For "their invention of 'symbolic model checking', a method of formally checking system designs widely used in the computer hardware industry". [6] |
1999 | Daniel Sleator and Robert Tarjan | For "invention of the widely used splay-tree data structure". [7] |
2000 | Narendra Karmarkar | For "his theoretical work in devising an interior point method for linear programming that provably runs in polynomial time, and for his implementation work suggesting that Interior Point methods could be effective for linear programming in practice as well as theory". [8] |
2001 | Eugene Myers | For "his contribution to sequencing the human genome, the complete DNA content of a human cell, and encoding all of its genes, the basic building blocks of life". [9] |
2002 | Peter Franaszek | For "his seminal and sustained contributions to the theory and application of constrained channel coding". [10] |
2003 | Gary Miller, Michael Rabin, Robert Solovay, and Volker Strassen | For "their contributions to realizing the practical uses of cryptography and for demonstrating the power of algorithms that make random choices", through work which "led to two probabilistic primality tests, known as the Solovay–Strassen test and the Miller–Rabin test". [11] |
2004 | Yoav Freund and Robert Schapire | For their "seminal work and distinguished contributions [...] to the development of the theory and practice of boosting, a general and provably effective method of producing arbitrarily accurate prediction rules by combining weak learning rules"; specifically, for AdaBoost, their machine learning algorithm, which "can be used to significantly reduce the error of algorithms used in statistical analysis, spam filtering, fraud detection, optical character recognition, and market segmentation, among other applications". [12] |
2005 | Gerard Holzmann, Robert Kurshan, Moshe Vardi, and Pierre Wolper | For "their contribution to techniques that provide powerful formal verification tools for hardware and software systems". [13] |
2006 | Robert Brayton | For "his innovative contributions to logic synthesis and electronic system simulation, which have made possible rapid circuit design technologies for the electronic design automation industry". [14] |
2007 | Bruno Buchberger | For "his role in developing the theory of Groebner bases, which has become a crucial building block to computer algebra, and is widely used in science, engineering, and computer science". [15] |
2008 | Corinna Cortes and Vladimir Vapnik | For "their revolutionary development of a highly effective algorithm known as support vector machines (SVM), a set of related supervised learning methods used for data classification and regression", which is "one of the most frequently used algorithms in machine learning, and is used in medical diagnosis, weather forecasting, and intrusion detection among many other practical applications". [16] |
2009 | Mihir Bellare and Phillip Rogaway | For "their development of practice-oriented provable security, which has resulted in high-quality, cost-effective cryptography, a key component for Internet security in an era of explosive growth in online transactions". [17] |
2010 | Kurt Mehlhorn | For "contributions to algorithm engineering that led to creation of the Library of Efficient Data types and Algorithms (LEDA)", a software collection of data structures and algorithms which "has been incorporated in the applied research programs of thousands of companies worldwide in telecommunications, bioinformatics, computer-aided design (CAD) and geographic information systems (GIS), banking, optical products, and transportation". [18] |
2011 | Hanan Samet | For "pioneering research on quadtrees and other multidimensional spatial data structures for sorting spatial information, as well as his well-received books, which have profoundly influenced the theory and application of these structures". [19] |
2012 | Andrei Broder, Moses S Charikar and Piotr Indyk | For "their groundbreaking work on locality-sensitive hashing that has had great impact in many fields of computer science including computer vision, databases, information retrieval, machine learning, and signal processing". [20] |
2013 | Robert D. Blumofe, and Charles E. Leiserson | For "contributions to efficient and robust parallel computation through both provably efficient randomized scheduling protocols and a set of parallel-language primitives constituting the Cilk framework". [21] They developed provably efficient randomized work stealing scheduling algorithms, and Cilk, a small set of linguistic primitives for programming multithreaded computations. [21] |
2014 | James Demmel | For "contributions to algorithms and software for numerical linear algebra used in scientific computing and large-scale data analysis." [22] |
2015 | Michael Luby | For "groundbreaking contributions to erasure correcting codes, which are essential for improving the quality of video transmission over the Internet." [23] |
2016 | Amos Fiat and Moni Naor | For "the development of broadcast encryption and traitor tracing systems". [24] [25] |
2017 | Scott Shenker | For "pioneering contributions to fair queueing in packet-switching networks, which had a major impact on modern practice in computer communication." [26] |
2018 | Pavel A. Pevzner | For "pioneering contributions to the theory, design, and implementation of algorithms for string reconstruction and to their applications in the assembly of genomes." [27] |
2019 | Noga Alon, Phillip Gibbons, Yossi Matias and Mario Szegedy | For "seminal work on the foundations of streaming algorithms and their application to large-scale data analytics." [28] |
2020 | Yossi Azar, Andrei Broder, Anna Karlin, Michael Mitzenmacher, and Eli Upfal | For "the discovery and analysis of balanced allocations, known as the power of two choices, and their extensive applications to practice." [29] |
2021 | Avrim Blum, Irit Dinur, Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith | For "fundamental contributions to the development of differential privacy." [30] |
The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membership group, claiming nearly 110,000 student and professional members as of 2022. Its headquarters are in New York City.
Leonard Adleman is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award. He is also known for the creation of the field of DNA computing.
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. He invented the fat-tree interconnection network, a hardware-universal interconnection network used in many supercomputers, including the Connection Machine CM5, for which he was network architect. He helped pioneer the development of VLSI theory, including the retiming method of digital optimization with James B. Saxe and systolic arrays with H. T. Kung. He conceived of the notion of cache-oblivious algorithms, which are algorithms that have no tuning parameters for cache size or cache-line length, but nevertheless use cache near-optimally. He developed the Cilk language for multithreaded programming, which uses a provably good work-stealing algorithm for scheduling. Leiserson coauthored the standard algorithms textbook Introduction to Algorithms together with Thomas H. Cormen, Ronald L. Rivest, and Clifford Stein.
Bruno Buchberger is Professor of Computer Mathematics at Johannes Kepler University in Linz, Austria. In his 1965 Ph.D. thesis, he created the theory of Gröbner bases, and has developed this theory throughout his career. He named these objects after his advisor Wolfgang Gröbner. Since 1995, he has been active in the Theorema project at the University of Linz.
Paris Christos Kanellakis was a Greek American computer scientist.
Andrei Zary Broder is a distinguished scientist at Google. Previously, he was a research fellow and vice president of computational advertising for Yahoo!, and before that, the vice president of research for AltaVista. He has also worked for IBM Research as a distinguished engineer and was CTO of IBM's Institute for Search and Text Analysis.
Phillip Rogaway is an American cryptographer who is a professor of computer science at the University of California, Davis. He graduated from Beverly Hills High School, and later earned a BA in computer science from UC Berkeley and completed his PhD in cryptography at MIT, in the Theory of Computation group. He has taught at UC Davis since 1994. He was awarded the Paris Kanellakis Award in 2009 and the first Levchin Prize for Real World Cryptography in 2016. Rogaway received an NSF CAREER award in 1996, which the NSA had attempted to prevent by influencing the NSF.
ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.
The W. Wallace McDowell Award is awarded by the IEEE Computer Society for outstanding theoretical, design, educational, practical, or related innovative contributions that fall within the scope of Computer Society interest. This is the highest technical award made solely by the IEEE Computer Society where selection of the awardee is based on the "highest level of technical accomplishment and achievement". The IEEE Computer Society is "dedicated to advancing the theory, practice, and application of computer and information processing technology." Another award considered to be the "most prestigious technical award in computing" is the A. M. Turing Award awarded by Association for Computing Machinery (ACM). This is popularly referred to as the "computer science's equivalent of the Nobel Prize". The W. Wallace McDowell Award is sometimes popularly referred to as the "IT Nobel".
Ernest Allen Emerson II, better known as E. Allen Emerson, is an American computer scientist and winner of the 2007 Turing Award. He is Professor and Regents Chair Emeritus at the University of Texas at Austin, United States.
Gary Lee Miller is a professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States. In 2003 he won the ACM Paris Kanellakis Award for the Miller–Rabin primality test. He was made an ACM Fellow in 2002 and won the Knuth Prize in 2013.
Piotr Indyk is Thomas D. and Virginia W. Cabot Professor in the Theory of Computation Group at the Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology.
Cynthia Dwork is an American computer scientist best known for her contributions to cryptography, distributed computing, and algorithmic fairness. She is one of the inventors of differential privacy and proof-of-work.
Pavel Arkadevich Pevzner is the Ronald R. Taylor Professor of Computer Science and director of the NIH Center for Computational Mass Spectrometry at University of California, San Diego. He serves on the editorial board of PLoS Computational Biology and he is a member of the Genome Institute of Singapore scientific advisory board.
Pierre Wolper is a Belgian computer scientist at the University of Liège. His research interests include verification methods for reactive and concurrent programs, as well as temporal databases. He is the co-recipient of the 2000 Gödel Prize, along with Moshe Y. Vardi, for his work on temporal logic with finite automata. He also received the 2005 Paris Kanellakis Award for this work.
Anna R. Karlin is an American computer scientist, the Microsoft Professor of Computer Science & Engineering at the University of Washington.
Dina Katabi is the Andrew and Erna Viterbi Professor of Electrical Engineering and Computer Science at MIT and the director of the MIT Wireless Center.
Moses Samson Charikar is an Indian computer scientist who works as a professor at Stanford University. He was previously a professor at Princeton University. The topics of his research include approximation algorithms, streaming algorithms, and metric embeddings. He is known for the creation of the SimHash algorithm used by Google for near duplicate detection.
Hanan Samet is a Computer Science researcher and Distinguished University Professor at the University of Maryland's Computer Science Department, which is part of the University of Maryland College of Computer, Mathematical, and Natural Sciences. He completed his PhD at Stanford University in 1975.