Prof. Technion israélien. remporte le prestigieux prix Turing d’un million de dollars
Considéré comme le « Prix Nobel d’informatique », le prix AM Turing 2024 sera décerné au professeur Avi Wigderson, diplômé de la faculté d’informatique Henry et Marilyn Taub de l’Institut de technologie Technion-Israël à Haïfa.
Il s’agit d’un prix annuel décerné par l’American Association for Computing Machinery (ACM). Le lauréat, dont le prix a été annoncé jeudi, est un chercheur en informatique de l’Institute for Advanced Study (IAS) de l’Université de Princeton dans le New Jersey.
En juin 2023, Wigderson a reçu un doctorat honorifique du Technion pour « sa contribution significative et son leadership dans les domaines de la théorie de l’informatique et des mathématiques discrètes, y compris la théorie de la complexité, la cryptographie, les graphes en expansion, et plus encore ; et en remerciement pour sa relation de longue date avec le Technion, à commencer par ses études de premier cycle.
L’ACM a déclaré lui avoir décerné ce prix prestigieux pour « ses contributions fondamentales à la théorie du calcul, notamment la refonte de notre compréhension du rôle du hasard dans le calcul, et pour ses décennies de leadership intellectuel en informatique théorique ».
Wigderson, né à Haïfa en 1956, a obtenu son diplôme de premier cycle à la Faculté d’informatique Taub du Technion en 1980. Il a ensuite obtenu une maîtrise et un doctorat à Princeton, où il est actuellement chercheur à l’Institute for Advanced Étude.
Au fil des années, il a publié des centaines d’articles et a remporté de nombreux prix et bourses, notamment la bourse Alon, le prix Gödel, le prix Knuth, le prix Abel et le prix Rolf Nevanlinna. Wigderson est également auteur. Son livre, Mathematics and Computation: A Theory Revolutionizing Technology and Science, rend le domaine de la complexité accessible et explique ses liens avec la théorie de l’informatique.
L’informatique théorique s’intéresse aux fondements mathématiques du domaine. Cela pose des questions telles que : « Ce problème peut-il être résolu par le calcul ? » » ou « Si ce problème peut être résolu par le calcul, combien de temps et d’autres ressources seront nécessaires ? » Il explore également la conception d’algorithmes efficaces. Chaque technologie informatique utilisée nécessite des algorithmes.
Comprendre les principes qui sous-tendent des algorithmes puissants et efficaces peut approfondir non seulement la compréhension de l’informatique, mais également des lois de la nature.
Même si l’informatique théorique est connue comme un domaine qui présente des défis intellectuels passionnants et qui n’est souvent pas directement concerné par l’amélioration des applications pratiques de l’informatique, les percées de la recherche dans cette discipline ont conduit à des progrès dans presque tous les domaines du domaine – de la cryptographie à la biologie computationnelle. à la conception de réseaux, à l’apprentissage automatique et à l’informatique quantique.
Comprendre les principes pour créer des algorithmes efficaces
Fondamentalement, les ordinateurs sont des systèmes déterministes ; l’ensemble des instructions d’un algorithme appliqué à une entrée donnée détermine de manière unique son calcul et, en particulier, sa sortie.
En d’autres termes, l’algorithme déterministe a un modèle prévisible. Le hasard, en revanche, manque de modèle bien défini ou de prévisibilité des événements ou des résultats.
Parce que le monde dans lequel nous vivons semble rempli d’événements aléatoires (systèmes météorologiques, phénomènes biologiques et quantiques, etc.), les informaticiens ont enrichi les algorithmes en leur permettant de faire des choix aléatoires au cours de leurs calculs, dans l’espoir d’améliorer leur efficacité. Notamment, de nombreux problèmes, pour lesquels aucun algorithme déterministe efficace n’était connu, ont été résolus efficacement par des algorithmes probabilistes, bien qu’avec une faible probabilité d’erreur (qui peut être efficacement réduite).
Ces questions, et bien d’autres, fondamentales, sont au cœur de la compréhension du caractère aléatoire et pseudo-aléatoire dans le calcul. Une meilleure compréhension de la dynamique du caractère aléatoire dans le calcul peut conduire au développement de meilleurs algorithmes ainsi qu’à une meilleure compréhension de la nature du calcul lui-même.
Pionnier de la recherche théorique en informatique depuis quatre décennies, Wigderson a apporté des contributions fondamentales à la compréhension du rôle du hasard et du pseudo-aléatoire dans le calcul.
Les informaticiens ont découvert un lien remarquable entre le caractère aléatoire et la difficulté de calcul (identifier des problèmes naturels pour lesquels aucun algorithme efficace n’est disponible). En collaboration avec des collègues, Wigderson est l’auteur d’une série d’ouvrages très influents sur l’échange de dureté contre le hasard. Ils ont prouvé que, sous des hypothèses informatiques standard et largement acceptées, tout algorithme probabiliste en temps polynomial peut être efficacement dérandomisé (c’est-à-dire rendu entièrement déterministe). En d’autres termes, le caractère aléatoire n’est pas nécessaire pour un calcul efficace.
Cette séquence de travaux a révolutionné la compréhension du rôle du hasard dans le calcul et la façon dont on pense le hasard.
En dehors de ses travaux sur le hasard, Wigderson a été un leader intellectuel dans plusieurs autres domaines de l’informatique théorique, notamment les preuves interactives multi-preuves, la cryptographie et la complexité des circuits.
En plus de ses contributions techniques révolutionnaires, Wigderson est reconnu comme un mentor et un collègue estimé qui a conseillé d’innombrables jeunes chercheurs. Ses vastes connaissances et ses compétences techniques inégalées, associées à sa convivialité, son enthousiasme et sa générosité, ont attiré de nombreux jeunes esprits talentueux, les incitant à poursuivre une carrière dans l’informatique théorique.
Le président du Technion, le professeur Uri Sivan, a félicité Wigderson et a déclaré : « Nous sommes très fiers du fait qu’il soit un ancien élève du Technion ayant un lien de longue date avec notre communauté de chercheurs. L’année dernière, nous lui avons décerné un doctorat honorifique pour sa contribution révolutionnaire à un large éventail de sujets, des mathématiques discrètes à la cryptographie complexe. Son obtention du prix Turing prouve que le monde reconnaît ses contributions fondamentales. Nous le félicitons pour cet immense honneur et nous nous réjouissons avec lui.
Le professeur Danny Raz, doyen de la faculté d’informatique de Taub, a ajouté : « Le professeur. Les immenses contributions de Wigderson aux domaines des mathématiques et de l’informatique lui ont valu une reconnaissance internationale. Il sert de modèle à nos diplômés, incarnant l’esprit du Technion en tant qu’ancien élève qui, depuis la fin de ses études, a consacré sa carrière à l’avancement des connaissances humaines. Un brillant chercheur en mathématiques et en informatique ; et à leur interface, il mérite vraiment cette récompense prestigieuse.
« Il est important de souligner qu’Avi Wigderson a également reçu le prix Abel, qui est considéré comme la distinction la plus importante pour l’œuvre de toute une vie dans le domaine des mathématiques », a expliqué le président de l’ACM, Yannis Ioannidis.
« Être sélectionné pour le prix ACM AM Turing est une suite tout à fait appropriée, car les mathématiques sont fondamentales pour l’informatique et les travaux de Wigderson ont relié un large éventail de sous-domaines mathématiques à l’informatique théorique.
« Il constitue une force intellectuelle imposante en informatique théorique, une discipline passionnante qui attire certains des jeunes chercheurs les plus prometteurs pour travailler sur les défis les plus difficiles. Le prix Turing de cette année récompense son travail spécifique sur le hasard ainsi que son impact indirect mais substantiel [Wigderson] a eu sur l’ensemble du domaine de l’informatique théorique », a souligné Ioannidis.