Depuis plus de 40 ans, Avi Wigderson étudie les problèmes. Mais en tant que théoricien de la complexité informatique, il ne se soucie pas nécessairement des réponses à ces problèmes. Il veut souvent simplement savoir s'ils peuvent être résolus ou non, et comment le savoir. "La situation est ridicule", a déclaré Wigderson, informaticien à l'Institute for Advanced Study de Princeton, New Jersey. Aussi difficile qu’une question puisse paraître, un moyen efficace d’y répondre pourrait se cacher hors de portée. « Pour autant que nous le sachions, pour chaque problème auquel nous sommes confrontés et que nous essayons de résoudre, nous ne pouvons pas exclure qu'il existe un algorithme capable de le résoudre. C’est le problème le plus intéressant pour moi.

Aujourd'hui, Wigderson a été nommé vainqueur du Prix ​​AM Turing, largement considéré comme l'une des plus hautes distinctions en informatique, pour ses contributions fondamentales à la théorie du calcul. Le travail de Wigderson a touché presque tous les domaines du domaine. Ses collègues, collaborateurs et mentorés disent qu'il trouve constamment des ponts inattendus entre des domaines disparates. Et ses travaux sur le hasard et le calcul, entrepris dans les années 1990, ont révélé des liens profonds entre les mathématiques et l'informatique qui sous-tendent les recherches actuelles.

Madhu Soudan, un informaticien de l'Université Harvard qui a remporté le prix Rolf Nevanlinna en 2002 (maintenant appelé prix Abacus), a déclaré que l'influence de Wigderson dans ce domaine était impossible à ignorer. "Il est très difficile de travailler dans n'importe quel domaine de l'informatique sans réellement croiser le travail d'Avi", a déclaré Soudan. « Et partout, vous trouvez des idées très profondes. » À la fin des années 1980, par exemple, Soudan a travaillé avec Wigderson sur un article étudiant les liens entre certaines fonctions mathématiques et polynômes. Ce travail a lancé toute la carrière du Soudan. "C'est typique d'Avi", a déclaré Soudan. "Il entre dans un espace, il pose les bonnes questions, puis il passe à autre chose."

Wigderson a grandi à Haïfa, en Israël, comme l'un des trois fils d'une infirmière et d'un ingénieur électricien, tous deux survivants de l'Holocauste. Son père adorait les puzzles et s'intéressait énormément aux idées fondamentales des mathématiques, qu'il partageait avec ses enfants. "C'est lui qui m'a infecté par ce virus", a déclaré Wigderson. Lorsqu’il a commencé ses études universitaires dans les années 1970, au Technion de Haïfa, il souhaitait se spécialiser en mathématiques, mais ses parents l’ont plutôt orienté vers l’informatique. "Ils pensaient que c'était peut-être une bonne idée que j'aie un emploi une fois que j'aurai fini", a-t-il déclaré.

Il a découvert un domaine riche en questions profondes et sans réponse, qui étaient fondamentalement mathématiques. L’un de ses premiers efforts novateurs s’est concentré sur une contradiction apparente : s’il était possible de convaincre quelqu’un d’autre qu’un énoncé mathématique avait été prouvé sans montrer comment.

"La personne qui voit la preuve n'apprend rien sur la preuve elle-même", a déclaré Couru Raz, informaticien à l'Université de Princeton. En 1985, Shafi Goldwasser, Silvio Micali et Charles Rackoff ont introduit ce concept de preuves interactives sans connaissance, démontrant son utilisation pour quelques déclarations. Wigderson, avec Micali et Oded Goldreich, a ensuite exposé cette idée, exposant les conditions montrant que si une déclaration peut être prouvée, elle a également une preuve de connaissance nulle.

« Il s’agit d’un résultat clé en cryptographie ; c'est extrêmement central », a déclaré Raz. Grâce à une preuve sans connaissance, quelqu'un peut prouver qu'il a correctement chiffré ou signé un message à l'aide de sa clé secrète, sans révéler aucune information à ce sujet. "Avi a des résultats extrêmement importants en cryptographie, et celui-ci est peut-être le plus important d'entre eux."

Mais le résultat le plus fondamental de Wigderson réside peut-être dans un autre domaine : relier la dureté informatique à aléatoire. À la fin des années 1970, les informaticiens avaient réalisé que, pour de nombreux problèmes difficiles, les algorithmes faisant appel au hasard, également appelés algorithmes probabilistes, pouvaient largement surpasser leurs alternatives déterministes. Dans un Preuve 1977, par exemple, Robert Solovay et Volker Strassen ont introduit un algorithme aléatoire capable de déterminer si un nombre est premier plus rapidement que les meilleurs algorithmes déterministes de l'époque.

Pour certains problèmes, les algorithmes probabilistes peuvent en indiquer des problèmes déterministes. Au début des années 1980, Wigderson a travaillé avec Richard Karp de l'Université de Californie à Berkeley pour relier l'idée du hasard à des problèmes considérés comme difficiles en termes de calcul, ce qui signifie qu'aucun algorithme déterministe connu ne peut les résoudre dans un délai raisonnable. "Nous ne savons pas comment prouver qu'ils sont durs", a déclaré Wigderson. Cependant, lui et Karp ont trouvé un algorithme aléatoire pour un certain problème difficile qu'ils ont ensuite pu dérandomiser, découvrant ainsi un algorithme déterministe pour celui-ci. À peu près à la même époque, d’autres chercheurs ont montré comment les hypothèses de dureté informatique dans les problèmes de cryptographie pouvaient permettre la dérandomisation en général.

L’efficacité déraisonnable du hasard l’a amené à réfléchir à la nature même du hasard. Comme d’autres chercheurs de l’époque, il s’est demandé à quel point il était nécessaire pour résoudre efficacement les problèmes et dans quelles conditions il pouvait être complètement éliminé. "Au départ, il n'était pas clair si c'était seulement notre propre stupidité et si nous ne pouvions pas éliminer le hasard", a-t-il déclaré. "Mais la plus grande question était de savoir si le caractère aléatoire peut toujours être éliminé de manière efficace ou non." Il s’est rendu compte que le besoin de caractère aléatoire était intimement lié à la difficulté informatique du problème.

Pour une papier 1994, lui et l'informaticien Noam Nisan ont éclairé ce lien. Ils ont prouvé que s’il existe des problèmes naturels difficiles, comme le soupçonnent la plupart des informaticiens, alors tout algorithme randomisé efficace peut être remplacé par un algorithme déterministe efficace. "Vous pouvez toujours éliminer le hasard", a déclaré Wigderson.

Plus important encore, ils ont découvert que les algorithmes déterministes peuvent utiliser des séquences « pseudo-aléatoires », c'est-à-dire des chaînes de données qui semblent aléatoires mais ne le sont pas. Ils ont également montré comment des problèmes difficiles peuvent être utilisés pour construire un générateur pseudo-aléatoire. L'introduction des bits pseudo-aléatoires (au lieu des bits aléatoires) dans un algorithme probabiliste aboutira à un algorithme déterministe efficace pour le même problème.

Le Soudan a déclaré que cet article aidait les informaticiens à reconnaître les degrés de hasard qui pourraient aider à révéler les subtilités de problèmes difficiles et comment les résoudre. "Il ne s'agit pas seulement de hasard, mais de perceptions du hasard", a-t-il déclaré. "C'est la clé."

Le Soudan souligne que le hasard semble apparaître partout mais qu’il est, en réalité, extrêmement difficile à trouver. "Les gens vous disent que les chiffres de pi semblent aléatoires, ou que la séquence de nombres premiers semble aléatoire", a-t-il déclaré. "Ils sont complètement déterminés, mais ils nous semblent aléatoires." La perception du hasard, dit-il, est aujourd’hui au cœur de l’informatique. "Et c'est quelque chose qu'Avi a largement promu."

Le hasard est devenu une ressource puissante dans la théorie de la complexité, mais il reste insaisissable. Wigderson souligne que les lancers de pièces et de dés ne sont pas vraiment aléatoires : si vous disposez de suffisamment d’informations sur le système physique, le résultat est entièrement prévisible. Le hasard parfait, dit-il, est insaisissable et difficile à vérifier.

Mais pour Wigerson, les exemples d’informatique sont omniprésents – pas seulement dans les smartphones, les ordinateurs portables et les algorithmes de chiffrement, mais également dans les systèmes biologiques et physiques. Au cours des dernières décennies, les découvertes de la théorie informatique ont donné un aperçu d’une série de problèmes inattendus, allant des essaims d’oiseaux aux résultats des élections en passant par les réactions biochimiques dans le corps. « Fondamentalement, tout processus naturel est une évolution que vous pouvez considérer comme un calcul, vous pouvez donc l’étudier en tant que telle. Presque tout se calcule.