Le prix Turing 2023 de l’ACM décerné au professeur Avi Wigderson

• L’informatique théorique traite des fondements mathématiques de l’informatique. Elle pose des questions telles que : « Ce problème peut-il être résolu par le calcul ? », « Si ce problème peut être résolu par le calcul, combien de temps et de ressources cela nécessite-t-il ? ». Elle explore aussi les méthodes de conception d’algorithmes efficaces. Toutes les technologies informatiques qui influencent notre vie reposent sur des algorithmes. Comprendre les principes des algorithmes puissants et efficaces approfondit non seulement notre compréhension de l’informatique, mais aussi celle des lois de la nature. L’informatique théorique est connue comme un domaine proposant des défis intellectuels passionnants et, bien qu’elle ne soit souvent pas directement liée à l’amélioration des applications pratiques du calcul, les innovations de recherche dans ce domaine ont conduit à des avancées dans presque tous les secteurs, notamment la cryptographie, la biologie computationnelle, la conception de réseaux, l’apprentissage automatique et l’informatique quantique.

• Fondamentalement, un ordinateur est un système déterministe. Lorsqu’un ensemble d’instructions algorithmiques est appliqué à une entrée donnée, le calcul est déterminé de manière unique, et en particulier sa sortie l’est aussi. Autrement dit, un algorithme déterministe suit un schéma prévisible. À l’inverse, l’aléa se caractérise par l’absence de schéma bien défini ou de prévisibilité des événements/résultats. Comme le monde dans lequel nous vivons semble rempli d’événements aléatoires (systèmes météorologiques, phénomènes biologiques ou quantiques, etc.), les informaticiens ont enrichi les algorithmes pour leur permettre d’effectuer des choix aléatoires au cours du calcul afin d’en améliorer l’efficacité. En pratique, de nombreux problèmes pour lesquels aucun algorithme déterministe efficace n’est connu ont été résolus efficacement par des algorithmes probabilistes (avec une faible probabilité d’erreur, mais qu’il est possible de réduire efficacement). Mais l’aléa est-il indispensable, ou peut-il être éliminé ? Quelle qualité d’aléa est nécessaire au succès des algorithmes probabilistes ?

• Le Dr Avi Wigderson est à l’avant-garde de la recherche en informatique théorique depuis 40 ans et a apporté des contributions fondamentales à la compréhension du rôle de l’aléa et du pseudo-aléatoire dans le calcul. Les informaticiens ont découvert un lien remarquable entre l’aléa et la difficulté computationnelle (l’identification de problèmes naturels pour lesquels il n’existe pas d’algorithmes efficaces). Le Dr Wigderson, avec ses collègues, a mené une série de travaux extrêmement influents sur l’échange de difficulté contre de l’aléa. Ils ont démontré que, sous des hypothèses de calcul standard et largement admises, tout algorithme probabiliste en temps polynomial peut éliminer efficacement l’aléa (c’est-à-dire devenir entièrement déterministe). En d’autres termes, l’aléa n’est pas indispensable au calcul efficace. Cette série de travaux a révolutionné notre compréhension du rôle de l’aléa dans le calcul et notre manière de penser l’aléa.

Contributions du Dr Wigderson

• "Hardness vs. Randomness" (coécrit avec Noam Nisan) : cet article a notamment introduit un nouveau type de générateur pseudo-aléatoire et a démontré qu’une simulation déterministe efficace d’algorithmes randomisés est possible sous des hypothèses bien plus faibles que celles connues auparavant.

• "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (coécrit avec László Babai, Lance Fortnow et Noam Nisan) : cet article a montré, à l’aide de la "hardness amplification", que bounded-error probabilistic polynomial time (BPP) peut être simulé en temps subexponentiel pour une infinité de tailles d’entrée sous des hypothèses plus faibles.

• "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (coécrit avec Russell Impagliazzo) : cet article a présenté un générateur pseudo-aléatoire plus puissant avec un compromis hardness vs randomness essentiellement optimal.

• Au-delà de ses travaux sur l’aléa, le Dr Wigderson a aussi exercé un leadership intellectuel dans plusieurs autres domaines de l’informatique théorique, comme les preuves interactives à multiples prouveurs, la cryptographie et la complexité des circuits.

L’avis de GN⁺

• Les travaux de Wigderson, qui ont démontré d’un point de vue mathématique la relation entre aléa et complexité de calcul, revêtent une grande importance en tant que rencontre entre l’informatique et les mathématiques. En particulier, le fait d’avoir montré que de nombreux algorithmes dépendant de l’aléa peuvent en réalité être implémentés de manière équivalente et déterministe est considéré comme l’ouverture d’un nouvel horizon pour l’informatique.

• En outre, l’approche mathématique de la relation entre efficacité et difficulté semble appelée à devenir un sujet majeur de recherche en informatique théorique. L’idée que plus un problème est difficile, plus il pourrait exister en contrepartie un algorithme efficace n’est pas une intuition évidente.

• Par ailleurs, le fait que le professeur Wigderson ait insisté sur l’articulation entre mathématiques et informatique pour faire progresser l’informatique théorique, tout en s’investissant dans la formation des générations suivantes, apparaît comme un excellent exemple pour la relève académique. Son parcours, marqué notamment par l’obtention à la fois du prix Abel en mathématiques et du prix Turing en informatique, constitue un cas symbolique montrant l’importance de l’informatique théorique.

[GN⁺]

Avis Hacker News

• Avi Wigderson a reçu l’ACM A.M. Turing Award 2023. Cette distinction salue ses contributions fondamentales à la théorie du calcul, en particulier sa refonte de la compréhension du rôle de l’aléa dans le calcul, ainsi que son leadership intellectuel exercé pendant des décennies dans le domaine de l’informatique théorique.

• Wigderson a été une figure de proue dans des domaines tels que la théorie de la complexité computationnelle, les algorithmes et l’optimisation, l’aléa et la cryptographie, le calcul parallèle et distribué, la combinatoire et la théorie des graphes. Il a également servi de trait d’union entre l’informatique théorique, les mathématiques et les sciences.

• L’un des principaux accomplissements de Wigderson est la découverte d’un lien remarquable entre l’aléa et la difficulté computationnelle. Ses travaux ont montré que l’aléa n’est pas nécessairement indispensable à un calcul efficace.

• En 2021, il a également reçu le prix Abel, ce qui lui confère un parcours unique avec les plus hautes distinctions à la fois en mathématiques théoriques/abstraites et en informatique.

• Son livre "Mathematics and Computation" est paru récemment et reçoit un accueil très favorable.

• Selon les résultats de ses recherches, si une proposition est démontrable, alors une preuve à divulgation nulle de connaissance (zero-knowledge proof) est également possible, et l’application de nombres pseudo-aléatoires à des algorithmes probabilistes permet d’obtenir un algorithme déterministe efficace pour le même problème. Cela suggère qu’il est possible de réduire fortement la complexité de modèles de calcul probabilistes, notamment en IA.