Prix Donald E. Knuth

Prix Donald E. Knuth
Date de création	1996

Le prix Knuth récompense les scientifiques ayant apporté une contribution exceptionnelle en informatique théorique. Il porte le nom de Donald E. Knuth, l'un des plus grands contributeurs à l'informatique théorique.

Sur cette photo, Gary L. Miller, à gauche, lauréat du prix Knuth 2013, présente Volker Strassen, lauréat 2008, à la conférence SODA 2009.

Le prix Knuth est attribué tous les dix-huit mois, depuis 1996 ; il inclut une récompense de 5 000 USD. Le prix est attribué par le groupe d'intérêt SIGACT de l'ACM et le comité technique d'informatique théorique de l'IEEE. Les prix sont attribués en alternance au colloque ACM STOCS (Symposium on Theory of Computing) et à la conférence IEEE FOCS (Symposium on Foundations of Computer Science) qui sont parmi les conférences les plus prestigieuses d'informatique théorique. Contrairement au prix Gödel qui récompense les articles exceptionnels, le prix Knuth est attribué aux individus.

Récipiendaires

• 1996 - Andrew Chi-Chih Yao
• 1997 - Leslie Valiant
• 1999 - László Lovász
• 2000 - Jeffrey D. Ullman
• 2002 - Christos Papadimitriou
• 2003 - Miklos Ajtai
• 2005 - Mihalis Yannakakis
• 2007 - Nancy Lynch
• 2008 - Volker Strassen
• 2010 - David Johnson
• 2011 - Ravi Kannan
• 2012 - Leonid Levin
• 2013 - Gary L. Miller
• 2014 - Richard J. Lipton
• 2015 - László Babai, pour ses travaux sur les preuves interactives, la notion de preuve, et les implications en théorie de la complexité
• 2016 - Noam Nisan, pour son travail en complexité de la communication, sur les générateurs de nombres pseudo-aléatoires, les preuves interactives, et en théorie algorithmique des jeux.
• 2017 - Oded Goldreich, pour ses avancées en cryptographie, théorie de l’aléa, des preuves interactives, théorie de l'inapproximabilité, en test de propriété et en théorie de la complexité.
• 2018 - Johan Håstad pour ses travaux en optimisation, cryptographie, calcul parallèle et theorie de la complexité, en particulier ses travaux sur les circuits booléens, le théorème PCP, des résultats d'inapproximabilité et les générateurs pseudo-aléatoires.
• 2019 - Avi Wigderson, pour ses travaux sur les algorithmes probabilistes, la dérandomisation de la classe BPP, les preuves à divulgation nulle de connaissance, les systèmes de preuve interactive (menant au théorème PCP), les algorithmes parallèles,et les graphes expanseurs.
• 2020 - Cynthia Dwork, pour avoir transformé plusieurs domaines de l'informatique théorique, notamment le calcul distribué, la cryptographie, la confidentialité des données et plus récemment le biais algorithmique. Elle est surtout connu pour l'introduction de la notion de confidentialité différentielle, ses travaux sur la malléabilité en cryptographie, la cryptographie à base de treillis (en), la composition concurrente, et les preuves de travail.
• 2021 - Moshe Vardi, pour ses contributions en théorie des automates, en vérification, en théorie des bases de données, en complexité descriptive et sur la notion de connaissance dans les systèmes distribués.
• 2022 - Noga Alon, pour ses contributions fondamentales en combinatoire et en théorie des graphes et des applications à des sujets fondamentaux de l'informatique.
• 2023 - Éva Tardos, pour ses contributions soutenues à la définition et à l'évolution de plusieurs domaines de l'algorithmique, notamment ses travaux fondamentaux sur les algorithmes combinatoires, les algorithmes d'approximation et la théorie des jeux.

Lien externe

• Liste des récipiendaires sur la page du sigact.