Avi Wigderson (hébreu : אבי ויגדרזון ; né le 9 septembre 1956) est un informaticien et mathématicien israélien. Il est professeur Herbert H. Maass à l'école de mathématiques de l'Institute for Advanced Study à Princeton, dans le New Jersey, aux États-Unis. Ses intérêts de recherche incluent la théorie de la complexité computationnelle, les algorithmes parallèles, la théorie des graphes, la cryptographie et le calcul distribué. Wigderson a reçu le prix Abel en 2021 et le prix Turing en 2023 pour ses travaux transformateurs en informatique théorique.
Les travaux de Wigderson se concentrent sur le rôle du hasard dans le calcul et la structure des algorithmes efficaces. Il est une figure de proue de la théorie de la complexité, ayant apporté des contributions cruciales à la compréhension de la puissance des algorithmes randomisés, à la construction de graphes expanseurs via le produit zig-zag, et aux fondements des preuves à divulgation nulle de connaissance.
Vie et éducation
Wigderson est né à Haïfa, en Israël, le 9 septembre 1956, de survivants de l'Holocauste. Il a fréquenté l'école hébraïque Reali à Haïfa. En 1977, il a commencé ses études de premier cycle à l'Institut de technologie Technion d'Israël, où il a obtenu son diplôme en 1980. Au Technion, il a rencontré sa femme, Edna. Il a ensuite poursuivi des études supérieures à l'Université de Princeton, obtenant un doctorat en informatique en 1983. Sa thèse de doctorat, intitulée « Studies in Computational Complexity », a été supervisée par Richard Lipton. Wigderson est crédité d'avoir considérablement enrichi le domaine de la complexité computationnelle.
Carrière académique
Après avoir occupé des postes de courte durée à l'Université de Californie, Berkeley, au centre de recherche IBM Almaden à San Jose, en Californie, et à l'Institut de recherche en sciences mathématiques à Berkeley, Wigderson est retourné en Israël en 1986 pour rejoindre le corps professoral de l'Université hébraïque de Jérusalem. Il a obtenu sa titularisation en 1987 et est devenu professeur titulaire en 1991. En 1999, il a également pris un poste à l'Institute for Advanced Study, et en 2003, il a abandonné son poste à l'Université hébraïque pour occuper le rôle de professeur Herbert H. Maass à l'Institut de Princeton.
À l'Institute for Advanced Study, Wigderson s'est concentré sur l'interaction entre la complexité computationnelle, les mathématiques et la cryptographie. Il a aidé à diriger une génération de chercheurs dans ces domaines.
Contributions clés
Wigderson a étudié la question fondamentale de savoir si le hasard est nécessaire pour un calcul efficace. Avec Noam Nisan et Russell Impagliazzo, Wigderson a montré que pour certains algorithmes qui reposent sur des tirages de pièces aléatoires, il existe un algorithme déterministe presque aussi rapide qui n'utilise pas de hasard, à condition que certaines conditions soient remplies. Cette ligne de recherche, fondée sur le concept de pseudorandomness, est une pierre angulaire de l'informatique théorique.
En travaillant avec Omer Reingold et Salil Vadhan, Wigderson a développé le produit zig-zag, une opération combinatoire sur les graphes qui combine des graphes plus petits pour produire des graphes plus grands et bien connectés. Ce concept relie la théorie de l'complexité, la théorie des graphes et la théorie des groupes, avec des applications allant de la compréhension de la navigation dans un labyrinthe à la construction de graphes expanseurs efficaces. Le produit zig-zag est devenu un outil majeur en informatique théorique.
Wigderson, avec Silvio Micali et Oded Goldreich, a démontré que les preuves à divulgation nulle de connaissance peuvent être utilisées pour vérifier des résultats publics sur des données secrètes sans révéler les secrets sous-jacents. Ce travail est une couche fondamentale pour la cryptographie moderne.
Prix et distinctions
Wigderson a reçu le prix Nevanlinna en 1994, un prix de l'Union mathématique internationale, pour ses travaux sur la complexité computationnelle. En 2009, il a partagé le prix Gödel pour la construction zig-zag de graphes. Il a été élu à l'Académie américaine des arts et des sciences en 2011 et comme membre de l'ACM en 2018 pour ses contributions à l'informatique théorique et aux mathématiques.
En 2019, Wigderson a obtenu le prix Knuth pour, entre autres, ses travaux sur le calcul randomisé, la complexité des circuits, la complexité des preuves et le calcul parallèle. Il a reçu le prix Abel en 2021 avec Laszlo Lovasz pour des contributions fondamentales à l'informatique théorique et aux mathématiques discrètes. En avril 2024, l'Association for Computing Machinery lui a décerné le prix Turing pour avoir remodelé la compréhension du hasard dans le calcul et pour des décennies de leadership en informatique théorique. Il a également reçu le prix Great Immigrant de la Carnegie Corporation en 2025.
Vie personnelle
Wigderson est marié à Edna, et ils ont un fils, Yuval, qui est professeur de mathématiques à l'Institut des sciences et technologies d'Autriche. Wigderson continue d'inspirer les chercheurs en herbe à travers son travail et son mentorat.