Knuth Prize

Gary Miller presents Volker Strassen with the 2008 Knuth Prize at SODA 2009

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.

History

The Knuth Prize has been awarded since 1996 and includes an award of US$5,000. The prize is awarded by ACM SIGACT and by IEEE Computer Society's Technical Committee on the Mathematical Foundations of Computing. Prizes are awarded in alternating years at the ACM Symposium on Theory of Computing and at the IEEE Symposium on Foundations of Computer Science, which are among the most prestigious conferences in theoretical computer science. The recipient of the Knuth Prize delivers a lecture at the conference.[1] For instance, David S. Johnson "used his Knuth Prize lecture to push for practical applications for algorithms."[2]

In contrast with the Gödel Prize, which recognizes outstanding papers, the Knuth Prize is awarded to individuals for their overall impact in the field.

Winners

Since the prize was instituted in 1996, it has been awarded to the following individuals, with the citation for each award quoted (not always in full):[3]

Year Laureate Citation
1996 Andrew Yao "fundamental research in computational complexity"[4]
1997 Leslie Valiant "far-reaching contributions to the study of computational complexity, parallel computation, and learning theory"[5]
1999 László Lovász "enormous influence on the theory of algorithms" and "fundamental discoveries that have became standard tools in theoretical computer science"[6]
2000 Jeffrey Ullman "sustained research contributions to Theoretical Computer Science, especially as it relates to applied areas of Computer Science such as compilers, parallelism, and databases; and for his contributions to Theoretical Computer Science education through textbooks and the mentoring of graduate students"[7]
2002 Christos Papadimitriou "for longstanding and seminal contributions to the foundations of computer science"[8]
2003 Miklós Ajtai "for numerous ground-breaking contributions to Theoretical Computer Science"[9][10]
2005 Mihalis Yannakakis "for numerous ground-breaking contributions to Theoretical Computer Science"[11]
2007 Nancy Lynch "for seminal and influential contributions to the theory of distributed computing"[12]
2008 Volker Strassen "for his seminal and influential contributions to efficient algorithms"[13]
2010 David Johnson "for his contributions to theoretical and experimental analysis of algorithms"[2][14][15][16]
2011 Ravi Kannan "provided theoretical computer science with many powerful new algorithmic techniques"[17]
2012 Leonid Levin "in recognition of four decades of visionary research in complexity, cryptography, and information theory"[18]
2013 Gary Miller "major impact on cryptography as well as number theory, parallel computing, graph theory, mesh generation for scientific computing, and linear system solving"[19]
2014 Richard Lipton "for inventing new computer science and mathematical techniques to tackle foundational and practical problems in a wide range of areas in graph algorithms, computaiton, communication, program testing, and DNA computing"[20][21]
2015 László Babai "for his fundamental contributions to theoretical computer science, including algorithm design and complexity theory"[22]
2016 Noam Nisan "for fundamental and lasting contributions to theoretical computer science in areas including communication complexity, pseudo-random number generators, interactive proofs, and algorithmic game theory"[23]
2017 Oded Goldreich "for fundamental and lasting contributions to theoretical computer science in many areas including cryptography, randomness, probabilistically checkable proofs, inapproximability, property testing as well as complexity theory in general"[24]
2018 Johan Håstad "for his long and sustained record of milestone breakthroughs at the foundations of computer science, with huge impact on many areas including optimization, cryptography, parallel computing, and complexity theory"[25]
2019 Avi Wigderson "for fundamental and lasting contributions to the foundations of computer science in areas including randomized computation, cryptography, circuit complexity, proof complexity, parallel computation, and our understanding of fundamental graph properties"[26][27]
2020 Cynthia Dwork "for fundamental and lasting contributions to computer science. Dwork is one of the most influential theoretical computer scientists of her generation. Her research has transformed several fields, most notably distributed systems, cryptography, and data privacy, and her current work promises to add fairness in algorithmic decision making to the list."[28][29][30][31]
2021 Moshe Vardi "for outstanding contributions that apply mathematical logic to multiple fundamental areas of computer science"[32][33][34]
2022 Noga Alon "for foundational contributions in combinatorics and graph theory and applications to fundamental topics in computer science"[35]
2023 Éva Tardos for "her extensive research contributions and field leadership, namely co-authoring an influential textbook, Algorithm Design, co-editing the Handbook of Game Theory, serving as editor-in-chief of the Journal of the ACM and the Society for Industrial and Applied Mathematics (SIAM) Journal of Computing and chairing program committees for several leading field conferences"[36]
2024 Rajeev Alur for "outstanding contributions to the foundations of computer science for his introduction of novel models of computation which provide the theoretical foundations for analysis, design, synthesis, and verification of computer systems"[37]

Selection Committees

Year Selection Committee
1996 Ronald Graham, (Chair AT&T Research), Joe Halpern (IBM Almaden Research Center), Kurt Mehlhorn (Max-Planck-Institut für Informatik), Nicholas Pippenger (University of British Columbia), Eva Tardos (Cornell University), Avi Wigderson (Hebrew University)
1997
1999 Allan Borodin, Ashok Chandra, Herbert Edelsbrunner, Christos Papadimitriou, Éva Tardos (chair), and Avi Wigderson
2000
2002
2003
2005 Richard Ladner, Tom Leighton, Laci Lovasz, Gary Miller, Mike Paterson and Umesh Vazirani (chair)
2007 Mike Paterson (Chair), Tom Leighton, Gary Miller, Anne Condon, Mihalis Yannakakis, Richard Ladner
2008
2010
2011
2012
2013
2014
2015 Russell Impagliazzo, (Chair, UCSD), Uriel Feige, (The Weizmann Institute of Science), Michel Goemans (MIT), Johan H˚astad (KTH Royal Institute of Technology), Anna Karlin (U. of Washington), Satish B Rao (UC Berkeley)
2016 Allan Borodin (U. Toronto), Uri Feige (Weizmann Institute), Michel Goemans (MIT, chair), Johan H˚astad (KTH), Satish Rao (UC Berkeley) and Shang-Hua Teng (USC).
2017 Allan Borodin, (Chair, U. of Toronto), Avrim Blum (CMU), Shafi Goldwasser (MIT and Weizmann Institute), Johan H˚astad (KTH – Royal Institute of Technology), Satish Rao (UC Berkeley), and Shanghua Teng (USC)
2018 Allan Borodin, (U. of Toronto), Alan Frieze (CMU), Avrim Blum (TTIC), Shafi Goldwasser (UC Berkeley), Noam Nisan (Hebrew U.) and Shang-Hua Teng (Chair, USC)
2019 Avrim Blum (Chair, TTIC), Alan Frieze (CMU), Shafi Goldwasser (UC Berkeley), Noam Nisan (Hebrew U.), Ronitt Rubinfeld (MIT and Tel Aviv U.), and Andy Yao (Tsinghua U.).
2020 Alan Frieze, Chair(CMU), Hal Gabow (U. of Colorado), Noam Nisan (Hebrew U.), Ronitt Rubinfeld (MIT), Eva Tardos (Cornell U.), Andy Yao (Tsinghua U.)
2021 Harold Gabow (Chair, U. Colorado), Noam Nisan (Hebrew U.), Dana Randall (Georgia Tech), Ronitt Rubinfeld (MIT), Madhu Sudan (Harvard U.), and Andy Yao (Tsinghua U.)
2022 Harold Gabow (U. Colorado), Monika Henzinger (U. Vienna), Kurt Mehlhorn (Max Planck Institute), Dana Randall (Chair, Georgia Tech), Madhu Sudan (Harvard U.), and Andy Yao (Tsinghua U.)
2023 David Eppstein (UC Irvine), Monika Henzinger (Chair, ISTA/U. Vienna), Kurt Mehlhorn (Max Planck Institute), Dana Randall (Georgia Tech), Madhu Sudan (Harvard U.), and Moshe Vardi (Rice U.)
2024 Edith Cohen (Google/Tel Aviv U.), David Eppstein (Chair, UC Irvine), Monika Henzinger (IST Austria), Kurt Mehlhorn (Max Planck Institute), Salil Vadhan (Harvard U.), and Moshe Vardi (Rice U.)

See also

References

  1. ^ Knuth Prize, IEEE Computer Society
  2. ^ a b In Memoriam: David S. Johnson, Computing Research Association, April 2016
  3. ^ "Knuth Prize". ACM SIGACT. September 23, 2021. Retrieved September 23, 2021.
  4. ^ SMU Panel Discussion on Creating the Future Through Computing with Distinguished Turing Award Panelists, Singapore Management University
  5. ^ Valiant Receives 2010 Turing Award (PDF), Notices of the American Mathematical Society (June/July 2011)
  6. ^ Shelton, Ji (March 29, 2021). "2021 Abel Prize winner was a Yale math and computer science mainstay". Yale News. Yale University. Retrieved April 24, 2022.
  7. ^ Shelton, Jim (March 31, 2021). "ACM Turing Award honors innovators who shaped computer programming: Aho and Ullman developed tools and seminal textbooks used by millions of software programmers". EurekAlert!. AAAS. Retrieved April 24, 2022.
  8. ^ Bernadette Young (8 Oct 2019), Professor Christos Papadimitriou Awarded the 2018 Harvey Prize, Columbia University, Engineering
  9. ^ SIGACT Annual Report July 2002 – June 2003; 1. Awards that were given out, ACM, 2003
  10. ^ 2003 Knuth Prize Miklos Ajtai, ACM, October 9, 2003
  11. ^ 2005 Knuth Prize Mihalis Yannakakis, ACM, May 1, 2006
  12. ^ Nancy Lynch Named Recipient of ACM Award for Contributions to Reliability of Distributed Computing, MIT Computer Science & Artificial Intelligence Lab, 4 April 2007
  13. ^ ACM SIGACT 2008 Knuth Prize Recognizes Strassen for Contributions to Efficient Algorithm Design, ACM, October 23, 2008
  14. ^ Linda Crane, David S. Johnson: In Memoriam, Columbia University, Computer Science
  15. ^ Lee L. Keener, David S. Johnson '67, Amherst Magazine
  16. ^ AT&T Labs Researcher to Receive ACM SIGACT Knuth Prize for Algorithm Innovations, ACM, March 2, 2010
  17. ^ Three Microsoft India researchers named ACM fellow, Illinois Intelligencer, 9 December 2016
  18. ^ Citation: 2012 Knuth Prize (PDF), ACM, July 15, 2012
  19. ^ ACM Awards Knuth Prize to Creator of Problem-Solving Theory and Algorithms, ACM, April 4, 2013
  20. ^ "ACM Awards Knuth Prize to Pioneer for Advances in Algorithms and Complexity Theory". Association for Computing Machinery. September 15, 2014. Archived from the original on September 20, 2014.
  21. ^ Tylor, Phillip (2014). "ACM, IEEE Taps Lipton for Prestigious Knuth Prize". News Center. Georgia Tech. Retrieved April 24, 2022.
  22. ^ 2015 Knuth Prize Citation for László Babai (PDF), ACM, May 17, 2015
  23. ^ ACM Awards Knuth Prize to Pioneer of Algorithmic Game Theory, ACM, September 8, 2016
  24. ^ 2017 Knuth prize is Awarded to Oded Goldreich (PDF), ACM, June 13, 2017
  25. ^ 2018 Knuth Prize is Awarded to Johan Håstad (PDF), ACM, August 6, 2018
  26. ^ Sue Gee (7 April 2019), Knuth Prize 2019 Awarded For Contributions To Complexity Theory
  27. ^ "Optimization, Complexity and Math ... using Gradient" – Knuth Prize Lecture, STOC 2019 – Avi Wigderson, March 3, 2020, archived from the original on 2021-12-14
  28. ^ Elizabeth Salazar (15 May 2020), Cynthia Dwork wins Knuth Prize for Outstanding Contributions to the Foundations of Computer Science, Harvard University
  29. ^ Leading authority on cryptography and data privacy receives Knuth Prize, American Association for the Advancement of Science, 2 June 2020
  30. ^ Knuth Prize Lecture – Cynthia Dwork, 25 November 2020, archived from the original on 2021-12-14
  31. ^ "Harvard Professor Receives Prize for Contributions to Theoretical Computer Science". HPC Wire. June 2, 2020. Retrieved April 24, 2022.
  32. ^ 2021 Knuth Prize is Awarded to Moshe Vardi (PDF), ACM, May 9, 2021
  33. ^ STOC 2021 – Knuth Prize talk: Logic and Computation – A Match Made in Heaven – Moshe Vardi, Jul 14, 2021, archived from the original on 2021-12-14
  34. ^ Boyd, Jade (May 27, 2021). "Moshe Vardi wins Knuth Prize". Jewish Herald-Voice. Retrieved April 24, 2022.
  35. ^ "2022 Knuth Prize Awarded to Noga Alon" (PDF). ACM Special Interest Group on Algorithms and Computation Theory. Retrieved July 2, 2022.
  36. ^ "Tardos honored with 2023 Knuth Prize". Retrieved June 24, 2023.
  37. ^ "2024 Knuth Prize: Rajeev Alur". ACM Special Interest Group on Algorithms and Computation Theory. Retrieved August 8, 2024.

Read other articles:

Rumah sakit Cane Hill

Rumah Sakit Cane HillSouth London and Maudsley NHS Foundation TrustFoto Cane Hill pada tahun 2009GeografiLokasiCoulsdon, Croydon, Inggris, United KingdomOrganisasiAsuransi kesehatanNHS EnglandJenisRumah sakit jiwaSejarahDibuka1882 (1882)Ditutup2008Pranala luarSitus webslam.nhs.ukDaftarRumah sakit di Britania RayaRumah sakit Cane Hill adalah sebuah rumah sakit jiwa di Coulsdon di sektor London dari Croydon. Tempat ini dimiliki oleh Otoritas London Raya untuk Pertanahan dan Properti. Sejar...

 

Pembagian administratif Malawi

Peta pembagian administratif tingkat pertama Malawi Pembagian administratif Malawi terdiri atas 3 region pada tingkat pertama dan 28 distrik pada tingkat kedua. lbsPembagian administratif AfrikaNegaraberdaulat Afrika Selatan Afrika Tengah Aljazair Angola Benin Botswana Burkina Faso Burundi Chad Eritrea Eswatini Etiopia Gabon Gambia Ghana Guinea Guinea Khatulistiwa Guinea-Bissau Jibuti Kamerun Kenya Komoro Republik Demokratik Kongo Republik Kongo Lesotho Liberia Libya Madagaskar Malawi Mali Ma...

 

Gretsch

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (décembre 2020). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». En pratique : Quelles sources sont attendues ?...

Sepphoris

Former village and archaeological site located in the Galilee region of Israel This article is about the former Palestinian village and modern archaeological site. For the modern Israeli moshav, see Tzippori. Diocaesarea redirects here. For other uses, see Diocaesarea (disambiguation). Place in Northern, IsraelSepphoris / Tzipori / Saffuriya צִפּוֹרִי‎ / صفورية‎Sepphoris / Tzipori / SaffuriyaCoordinates: 32°44′44″N 35°16′43″E / 32.74556°N ...

 

Sumida-gawa

Sumida-gawajaponais : 隅田川 Le fleuve Sumida du pont Suijin. Caractéristiques Longueur 23,5 km Bassin collecteur Ara river basin (d) Cours Embouchure Baie de Tokyo · Localisation Tokyo · Altitude 0 m · Coordonnées 35° 43′ 07″ N, 139° 48′ 26″ E Géographie Pays traversés Japon modifier  Le fleuve Sumida (隅田川, Sumida-gawa?) est un cours d'eau du Japon qui traverse le nord-est de Tokyo. Long de 23,5 km, il est un d...

 

イスラームにおける結婚

イスラームにおける結婚（イスラームにおけるけっこん）とは、二者の間で行われる法的な契約である。新郎新婦は自身の自由な意思で結婚に同意する。口頭または紙面での規則に従った拘束的な契約は、イスラームの結婚で不可欠だと考えられており、新郎と新婦の権利と責任の概要を示している[1]。イスラームにおける離婚は様々な形をとることができ、個�...

Gedung Pakuan

Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: Gedung Pakuan – berita · surat kabar · buku · cendekiawan · JSTOR Gedung Pakuan di malam hari, dari buku Satu Tahun Berdirinja Negara Pasundan terbitan 1949 Gedung Pakuan (Gedong Pakuan) saat ini merupakan ru...

 

Flemish Movement

Regionalist movement in Flanders, Belgium This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Flemish Movement – news · newspapers · books · scholar · JSTOR (December 2010) (Learn how and when to remove this message) Flemish strijdvlag as adopted by large parts of the Flemish Movement The Flemish Movement (Dutch...

 

Distretto di Polje

Questa voce sull'argomento Lubiana è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Distretto di Poljedistretto(SL) Četrtna skupnost Polje Distretto di Polje – Veduta LocalizzazioneStato Slovenia Regione statisticaSlovenia Centrale ComuneLubiana TerritorioCoordinate46°03′28.69″N 14°35′00.52″E / 46.057969°N 14.583478°E46.057969; 14.583478 (Distretto di Polje)Coordinate: 46°03′28.69″N 14°35′00.52″E...

森川智之

森川智之配音演员本名同上原文名森川 智之（もりかわ としゆき）罗马拼音Morikawa Toshiyuki昵称モリモリ[1]、帝王[1]国籍 日本出生 (1967-01-26) 1967年1月26日（57歲） 日本東京都品川區[1]（神奈川縣川崎市[2]、橫濱市[3]成長）职业配音員、旁白、歌手、藝人音乐类型J-POP出道作品外國人取向的日語教材代表作品但丁（Devil May Cry）D-boy（宇宙騎...

 

Cibiru, Bandung

CibiruKecamatanPeta lokasi Kecamatan CibiruNegara IndonesiaProvinsiJawa BaratKotaBandungPemerintahan • CamatH.Tatang Muhktar, M.SiPopulasi • Total59.921 -Jiwa jiwaKode Kemendagri32.73.25 Kode BPS3273110 Desa/kelurahan- Cibiru (Aksara Sunda Baku: ᮎᮤᮘᮤᮛᮥ) adalah sebuah kecamatan di Kota Bandung, Provinsi Jawa Barat, Indonesia. Letaknya di sebelah timur Kota Bandung. Batas wilayah Utara Kecamatan Cilengkrang, Kabupaten Bandung Timur laut Kecamatan Cileuny...

 

جميل بن معمر

جميل بن معمر معلومات شخصية اسم الولادة جميل بن عبد الله بن معمر العذري الميلاد سنة 659   وادي القرى[1]  الوفاة (ت. 82 هـ/701 م)مصر ابان ولاية عبد العزيز بن مروان الجنسية  الدولة الأموية الحياة العملية الاسم الأدبي جميل بثينة الفترة الدولة الاموية المهنة شاعر اللغات ال�...

الجمعة العظيمة

الجمعة العظيمة الصليب قبالة بين القربان الفارغ والمفتوح وغير المضاء بالنور، في حين نزع غطاء المذبح، وجميعها من علامات الحداد يوم الجمعة العظيمة في الكنيسة الرومانية الكاثوليكية. يسمى أيضًا جمعة الآلام، الجمعة الحزينة، الجمعة المقدسة، جمعة الصلبوت يحتفل به المسيحيون نو�...

 

Hampton bioregion

Bioregion in Western Australia HamptonWestern AustraliaSand dunes and dune scrub near EuclaThe interim Australian bioregions,with Hampton in redArea10,881.98 km2 (4,201.6 sq mi) Localities around Hampton: Nullarbor Nullarbor Nullarbor Coolgardie Hampton Great Australian Bight Mallee Great Australian Bight Great Australian Bight Hampton is an interim Australian bioregion located in southeastern coastal Western Australia, with a small portion (4%) extending into adjacent South Au...

 

Pondicherry

PDY redirects here. For the Turkish sociopolitical movement, see Gülen movement. This article is about the capital city. For the union territory, see Puducherry (union territory). For other uses, see Puducherry (disambiguation). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Pondicherry – news · newspapers · books...

Керченская площадь

Керченская площадьукр. Керченська площа Киев 50°29′43″ с. ш. 30°35′22″ в. д.HGЯO Общая информация Страна Украина РайонДнепровский район  Названа в честьКерчь   Медиафайлы на Викискладе Ке́рченская пло́щадь — площадь в городе Киеве, что находится на ...

 

Giovanna Mezzogiorno

Pour les articles homonymes, voir Mezzogiorno (homonymie). Giovanna Mezzogiorno Giovanna Mezzogiorno au Festival de Cannes 2010. Données clés Naissance 9 novembre 1974 (49 ans)Rome, Italie Nationalité Italienne Profession Actrice Films notables La Fenêtre d'en faceRendez-vous à PalermeVincere modifier Giovanna Mezzogiorno, née le 9 novembre 1974 à Rome, est une actrice italienne. Actrice multi-récompensée, elle est principalement connue pour ses rôles dans les films La Fenêtr...

 

Alberto Schieppati

Alberto SchieppatiNazionalità Italia Altezza184 cm Peso85 kg Sci alpino SpecialitàSlalom gigante Squadra Carabinieri Termine carriera2014   Modifica dati su Wikidata · Manuale Alberto Schieppati (Milano, 7 giugno 1981) è un ex sciatore alpino italiano, specialista dello slalom gigante e dal 2021 commentatore sportivo per la Rai. Indice 1 Biografia 1.1 Carriera sciistica 1.2 Altre attività 2 Palmarès 2.1 Coppa del Mondo 2.2 Coppa Europa 2.2.1 Coppa Europa - vittorie 2...

Blu-code

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) The topic of this article may not meet Wikipedia's notability guidelines for products and services. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to ...

 

Bois-de-Boulogne station

Railway station in Montreal, Quebec, Canada Bois-de-BoulogneGeneral informationLocation1000, Henri-Bourassa Blvd. WestMontreal, Quebec H3M 3G1[1]Coordinates45°32′25″N 73°40′38″W / 45.54028°N 73.67722°W / 45.54028; -73.67722Operated byExoPlatforms2 side platformsTracks2Connections  Société de transport de Montréal  Société de transport de LavalConstructionParkingNone[1]Bicycle facilities7 spaces[1]Other inform...