Paris Kanellakis Award

Last updated

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]

Contents

Winners

YearWinnersCitation
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 [ broken anchor ], 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]
2022 Michael Burrows, Paolo Ferragina, and Giovanni Manzini 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." [31]
2023 Guy Blelloch, Julian Shun, and Laxman DhulipalaFor "contributions to algorithm engineering, including the Ligra, GBBS, and Aspen frameworks which revolutionized large-scale graph processing on shared-memory machines." [32]

See also

Related Research Articles

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, reporting nearly 110,000 student and professional members as of 2022. Its headquarters are in New York City.

<span class="mw-page-title-main">Leonard Adleman</span> American computer scientist

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.

<span class="mw-page-title-main">Charles E. Leiserson</span> American computer scientist

Charles Eric Leiserson is a computer scientist and professor at Massachusetts Institute of Technology (M.I.T.). He specializes in the theory of parallel computing and distributed computing.

<span class="mw-page-title-main">Bruno Buchberger</span> Austrian mathematician (born 1942)

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.

<span class="mw-page-title-main">Gerard J. Holzmann</span> Dutch-American computer scientist

Gerard J. Holzmann is a Dutch-American computer scientist and researcher at Bell Labs and NASA, best known as the developer of the SPIN model checker.

<span class="mw-page-title-main">Paris Kanellakis</span> American computer scientist (1953–1995)

Paris Christos Kanellakis was a Greek American computer scientist.

<span class="mw-page-title-main">Andrei Broder</span> 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.

<span class="mw-page-title-main">Gary Miller (computer scientist)</span> American computer scientist

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.

Eli Upfal is a computer science researcher, currently the Rush C. Hawkins Professor of Computer Science at Brown University. He completed his undergraduate studies in mathematics and statistics at the Hebrew University, Israel in 1978, received an M.Sc. in computer science from the Feinberg Graduate School of the Weizmann Institute of Science, Israel in 1980, and completed his PhD in computer science at the Hebrew University in 1983 under Eli Shamir. He has made contributions in a variety of areas. Most of his work involves randomized and/or online algorithms, stochastic processes, or the probabilistic analysis of deterministic algorithms. Particular applications include routing and communications networks, computational biology, and computational finance.

<span class="mw-page-title-main">Cynthia Dwork</span> American computer scientist

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.

Guy Edward Blelloch is a professor of computer science at Carnegie Mellon University. He is known for his work in parallel algorithms.

<span class="mw-page-title-main">Pavel A. Pevzner</span> Russian-born American professor of computational mass spectrometry

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.

<span class="mw-page-title-main">Anna Karlin</span> American computer scientist

Anna R. Karlin is an American computer scientist, the Microsoft Professor of Computer Science & Engineering at the University of Washington.

<span class="mw-page-title-main">Dina Katabi</span> American computer scientist

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. She was designated as one of the world’s most influential women engineers by Forbes magazine.

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.

References

  1. 1 2 "Paris Kanellakis Theory and Practice Award". ACM. Archived from the original on 2013-03-30. Retrieved 2012-12-12.
  2. "ACM Paris Kanellakis Award" (PDF). Conduit. 5 (1). Brown CS Dept: 4. 1996.
  3. "ACM SIGs: SIG Project Fund (SPF)". ACM . Retrieved 2012-12-12.
  4. "The first Paris Kanellakis Theory and Practice Award goes to founders of public key cryptography" (Press release). ACM. 12 Feb 1997. Archived from the original on 2012-02-11. Retrieved 2012-12-12.
  5. "The ACM Paris Kanellakis Theory and Practice Award goes to pioneers in data compression" (Press release). ACM. 26 Mar 1998. Archived from the original on 2012-02-11. Retrieved 2012-12-12.
  6. "ACM bestows Kanellakis Award for development of 'symbolic model checking,' used in testing computer system designs" (Press release). ACM. 26 Mar 1999. Archived from the original on 2011-06-05. Retrieved 2012-12-12.
  7. "ACM Paris Kanellakis Theory and Practice Award 1999". ACM . Retrieved 2017-11-22.
  8. "Interior point" (Press release). ACM. 2000. Archived from the original on 2012-04-02. Retrieved 2012-12-12.
  9. "ACM honors developer of key software for sequencing the human genome" (Press release). ACM. 22 Jan 2002. Archived from the original on 2012-02-11. Retrieved 2012-12-12.
  10. "ACM honors Peter Franaszek for contributions to data encoding" (Press release). ACM. 21 May 2003. Archived from the original on 11 February 2012. Retrieved 2012-12-12.
  11. "ACM honors creators of methods to improve cryptography" (Press release). ACM. 24 May 2004. Archived from the original on 11 February 2012. Retrieved 2012-12-12.
  12. "ACM Paris Kanellakis Theory and Practice Award 2004". ACM . Retrieved 2017-11-22.
  13. "ACM honors creators of verification tools for software, hardware" (Press release). ACM. 15 Mar 2006. Retrieved 2012-12-12.
  14. "ACM honors electronic design automation technologies pioneer" (Press release). ACM. 29 Mar 2007. Archived from the original on 2012-12-02. Retrieved 2012-12-12.
  15. "ACM Kanellakis Award honors innovator of automated tools for mathematics" (Press release). ACM. 13 May 2008. Archived from the original on 2 May 2013. Retrieved 2012-12-12.
  16. "ACM awards recognize innovators in computer science" (Press release). ACM. 17 Mar 2009. Archived from the original on 2013-05-02. Retrieved 2012-12-12.
  17. "ACM awards recognize computer scientists for innovations that have real world impact" (Press release). ACM. 30 Mar 2010. Archived from the original on 2012-12-02. Retrieved 2012-12-12.
  18. "ACM honors computing innovators for advances in research, commerce and education" (Press release). ACM. 6 Apr 2011. Archived from the original on 2013-05-02. Retrieved 2012-12-12.
  19. "ACM honors computing innovators for advances in research, education, and industry" (Press release). ACM. 26 Apr 2012. Archived from the original on 2013-05-02. Retrieved 2012-12-12.
  20. "ACM Paris Kanellakis Theory and Practice Award 2012". ACM. Archived from the original on 2013-03-30. Retrieved 2013-05-05.
  21. 1 2 "ACM Paris Kanellakis Theory and Practice Award 2013". ACM . Retrieved 2017-11-22.
  22. "ACM Paris Kanellakis Theory and Practice Award 2014". ACM . Retrieved 2015-07-17.
  23. "ACM Paris Kanellakis Theory and Practice Award 2015". ACM . Retrieved 2016-04-29.
  24. "ACM Paris Kanellakis Theory and Practice Award 2016". ACM . Retrieved 2017-11-22.
  25. "ACM Honors Eminent Researchers for Technical Innovations: 2016 Recipients Made Contributions in Areas Including Big Data Analysis, Computer Vision, and Encryption". ACM . Retrieved 2017-11-22.
  26. "ACM Paris Kanellakis Theory and Practice Award: Scott J Shenker" . Retrieved 2019-05-16.
  27. "ACM Paris Kanellakis Theory and Practice Award: Pavel Pevzner" . Retrieved 2019-05-16.
  28. "Creators of Balanced Allocations Paradigm Receive Kanellakis Award".
  29. "Creators of Balanced Allocations Paradigm Receive Kanellakis Award".
  30. "Contributors to the Development of Differential Privacy Receive Kanellakis Award".
  31. "ACM Paris Kanellakis Theory and Practice Award recipients invented the BW-transform and the FM-index". awards.acm.org. Retrieved 2023-07-11.
  32. "Contributors to Algorithm Engineering Receive Kanellakis Award". awards.acm.org. Retrieved 2024-06-19.