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

 (awards.acm.org)
1 points par GN⁺ 2024-04-12 | 1 commentaires | Partager sur WhatsApp
  • L’ACM a désigné Avi Wigderson comme lauréat du prix ACM A.M. Turing 2023, en reconnaissance de ses travaux qui ont renouvelé la compréhension de la théorie du calcul et du rôle de l’aléa dans le calcul
  • Wigderson est Herbert H. Maass Professor à l’Institute for Advanced Study, et une figure majeure des théories de la complexité computationnelle, ainsi que des algorithmes, de la cryptographie, du calcul parallèle et distribué, de la combinatoire et de la théorie des graphes
  • Sa contribution centrale porte sur les travaux hardness for randomness, qui montrent que, sous des hypothèses de calcul largement admises, on peut simuler de façon déterministe des algorithmes probabilistes en temps polynomial
  • Les articles associés ont introduit des générateurs pseudo-aléatoires, des simulations en temps sous-exponentiel pour BPP et des compromis hardness-vs-randomness, avec un impact sur de nombreux domaines de l’informatique théorique
  • Le prix Turing, doté de 1 million de dollars grâce au soutien de Google, salue Wigderson non seulement pour ses résultats techniques, mais aussi pour son rôle de mentor auprès des jeunes chercheurs

Contexte de l’attribution du prix Turing ACM

  • L’ACM a choisi Avi Wigderson comme lauréat du prix ACM A.M. Turing 2023
  • Cette distinction récompense ses contributions fondamentales à la théorie du calcul, ses travaux qui ont refaçonné la compréhension du rôle de l’aléa dans le calcul, ainsi que son leadership intellectuel exercé pendant des décennies en informatique théorique
  • Wigderson est Herbert H. Maass Professor au département de mathématiques de l’Institute for Advanced Study à Princeton, dans le New Jersey

  • Principaux domaines d’activité

    • théorie de la complexité computationnelle
    • algorithmes et optimisation
    • aléa et cryptographie
    • calcul parallèle et distribué
    • combinatoire et théorie des graphes
    • liens entre informatique théorique et mathématiques/sciences
    • Le prix ACM A.M. Turing est souvent qualifié de « prix Nobel de l’informatique » et s’accompagne d’une dotation de 1 million de dollars financée par Google, Inc.
    • Le prix porte le nom du mathématicien britannique Alan M. Turing, qui a posé les fondements mathématiques de l’informatique

Les questions traitées par l’informatique théorique

  • L’informatique théorique porte sur les fondements mathématiques de l’informatique et s’intéresse à des questions comme : « Ce problème peut-il être résolu par le calcul ? » et « Si oui, combien de temps et de ressources cela nécessite-t-il ? »
  • Le domaine étudie aussi les principes de conception d’algorithmes efficaces
  • Les algorithmes constituent la base des technologies informatiques utilisées au quotidien
  • L’informatique théorique relève aussi des défis intellectuels qui n’améliorent pas immédiatement les applications pratiques, mais ses percées peuvent ensuite faire progresser de nombreux domaines
    • cryptographie
    • biologie computationnelle
    • conception de réseaux
    • apprentissage automatique
    • informatique quantique

Pourquoi l’aléa est important dans le calcul

  • Les ordinateurs sont fondamentalement des systèmes déterministes : pour une entrée donnée, l’ensemble des instructions d’un algorithme détermine de façon unique le calcul et la sortie
  • L’aléa désigne l’absence de motif clair ou de prévisibilité dans un événement ou un résultat
  • Le monde réel comporte de nombreux phénomènes apparemment aléatoires, comme les systèmes météorologiques, les phénomènes biologiques ou les phénomènes quantiques
  • Les informaticiens ont étendu les algorithmes pour qu’ils puissent effectuer des choix aléatoires au cours du calcul afin d’en améliorer l’efficacité
  • De nombreux problèmes pour lesquels aucun algorithme déterministe efficace n’était connu peuvent néanmoins être résolus efficacement par des algorithmes probabilistes avec une faible probabilité d’erreur
    • Cette probabilité d’erreur peut être réduite efficacement
  • Les questions clés sont de savoir si l’aléa est indispensable, s’il peut être éliminé, et quelle qualité d’aléa est nécessaire au succès des algorithmes probabilistes
  • Une meilleure compréhension du fonctionnement de l’aléa et du pseudo-aléa dans le calcul peut conduire à de meilleurs algorithmes et à une meilleure compréhension de la nature même du calcul

Contributions de recherche majeures de Wigderson

  • Wigderson est l’une des figures qui ont façonné l’informatique théorique depuis 40 ans, avec des contributions fondamentales à la compréhension du rôle de l’aléa et du pseudo-aléa dans le calcul
  • Les informaticiens ont découvert un lien important entre l’aléa et la difficulté computationnelle, c’est-à-dire l’identification de problèmes naturels pour lesquels il n’existe pas d’algorithme efficace
  • Wigderson et ses collaborateurs ont publié des travaux influents sur hardness for randomness
  • Ces travaux montrent que, sous des hypothèses computationnelles standard et largement admises, tous les algorithmes probabilistes en temps polynomial peuvent être dérandomisés efficacement
  • Ce résultat suggère que l’aléa n’est peut-être pas indispensable au calcul efficace
  • Cette ligne de recherche a transformé le rôle attribué à l’aléa dans le calcul et la manière de le concevoir

  • Trois articles majeurs

Étendue de l’impact et autres réalisations

  • Les trois articles de Wigderson ont eu un impact qui dépasse les seuls domaines de l’aléa et de la dérandomisation, en influençant de nombreuses branches de l’informatique théorique
  • Les idées développées dans ces articles ont ensuite été reprises dans des travaux influents de nombreux chercheurs majeurs
  • Dans cet article, avec Omer Reingold, Salil Vadhan et Michael Capalbo, il présente la première construction combinatoire efficace d’un expander graph
    • un expander graph est un graphe peu dense doté de fortes propriétés de connectivité
    • il a des applications importantes à la fois en mathématiques et en informatique théorique
  • Au-delà de l’aléa, Wigderson a aussi exercé un leadership intellectuel dans les domaines suivants
    • multi-prover interactive proofs
    • cryptographie
    • complexité des circuits

Mentorat et reconnaissance

  • Wigderson est reconnu non seulement pour ses contributions techniques décisives, mais aussi comme mentor et collègue respecté ayant accompagné de nombreux jeunes chercheurs
  • Son immense savoir, ses compétences techniques, son accessibilité, son enthousiasme et sa générosité sont souvent cités comme des facteurs ayant encouragé de brillants jeunes chercheurs à faire carrière en informatique théorique
  • Le président de l’ACM, Yannis Ioannidis, a rappelé que Wigderson avait également reçu le prix Abel, considéré comme la plus haute distinction pour l’ensemble d’une carrière en mathématiques
  • Ioannidis a estimé que les mathématiques sont au fondement de l’informatique et que les travaux de Wigderson ont relié plusieurs sous-domaines des mathématiques à l’informatique théorique
  • Jeff Dean, Senior Vice President chez Google, a déclaré que les recherches de Wigderson sur l’aléa et d’autres sujets avaient défini l’agenda de l’informatique théorique au cours des 30 dernières années
  • Dean a également souligné le rôle de mentor de Wigderson, qui a su faire émerger des idées et des orientations de recherche, puis motiver de jeunes chercheurs à travailler dans ces directions

Prix Turing et autres articles majeurs de Wigderson

  • Le prix A.M. Turing, créé en 1966, distingue des informaticiens et ingénieurs ayant contribué aux systèmes et aux fondements théoriques qui ont façonné l’industrie des technologies de l’information
  • Le palmarès de Wigderson comprend notamment
    • prix Abel
    • médaille Abacus de l’IMU, anciennement prix Nevanlinna
    • prix Donald E. Knuth
    • prix Edsger W. Dijkstra en informatique distribuée
    • prix Gödel
  • Wigderson est ACM Fellow et membre de la U.S. National Academy of Sciences ainsi que de l’American Academy of Arts and Sciences

  • Autres articles majeurs

À lire aussi

1 commentaires

 
GN⁺ 2024-04-12
Commentaires sur Hacker News

  • Deux des principaux articles de Wigderson mentionnés dans l’annonce sont coécrits avec Noam Nisan, l’un des professeurs à l’origine du célèbre cours en ligne From Nand to Tetris

    • Le professeur Nisan est lui aussi remarquable. Après des résultats de premier plan en théorie du calcul, il a aussi eu un grand impact dans un domaine assez différent, la théorie algorithmique des jeux
      C’est appréciable de voir qu’une même personne peut accomplir des choses aussi variées, et le système qui a permis une telle souplesse est lui aussi impressionnant
    • Il y a aussi un livre. La 2e édition est sortie récemment

  • Il y a aussi un bon article de Quanta : https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    Les poses qu’on a fait prendre à Wigderson sont assez variées, c’était amusant. Ça a l’air très maladroit. Un peu dans le genre : « Allez, asseyez-vous sur cette chaise et regardez pensivement par la fenêtre »

    • Le passage expliquant que « l’efficacité déraisonnable du hasard » a amené Wigderson à réfléchir à la nature même du hasard est intéressant
      Je comprends les classes de complexité comme traitant des performances au pire cas, mais même avec un bon générateur pseudo-aléatoire et un bon algorithme randomisé, j’aimerais avoir une idée générale de la manière dont on prouve qu’aucune combinaison de RNG + seed + problem instance ne demande un temps exponentiel
    • D’après le rectificatif, l’article original disait que Wigderson avait fréquenté l’University of Haifa, alors qu’en réalité il est diplômé du Technion à Haïfa, en Israël
      Je me demande comment le journaliste a pu les confondre
    • La pose « assis sur une chaise à regarder par la fenêtre » fait très Martin Scorsese ou Sopranos. On dirait un vieux gangster dans une maison de retraite

  • Scott Aaronson a écrit un billet sur l’influence qu’une conférence d’Avi Wigderson a eue sur son orientation de carrière : https://scottaaronson.blog/?p=2925

  • Il y a plus d’informations dans « Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness » : [1] et une archive [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • Je me demande par où commencer pour rattraper les travaux de Wigderson sur le compromis entre difficulté et hasard
    Il est rare que je n’aie jamais entendu parler d’un lauréat du prix Turing, mais cette personne m’était complètement sortie du radar

    • Son livre est un bon point de départ : https://www.math.ias.edu/avi/book
    • Je me demande ce qu’on entend par « hypothèses de calcul standard et largement admises »
      J’imagine que cela veut dire qu’une approximation probabiliste d’un problème NP-complet n’est pas non plus en temps polynomial, mais je ne sais pas si cela veut plutôt dire que la version dérandomisée reste malgré tout un algorithme d’approximation

  • Je viens de commencer le livre de Wigderson et pour l’instant il me plaît bien : https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • Pour un usage personnel, de recherche ou d’enseignement, on peut consulter ici la version finale provisoire du livre : https://www.math.ias.edu/avi/book
    • J’ai regardé le livre, et il semble davantage adapté à des étudiants de master ou à des étudiants avancés en licence
      Je me demande si quelqu’un peut recommander un livre traitant les sujets du calcul de façon plus élémentaire pour quelqu’un dont les bases de licence en informatique/mathématiques sont un peu rouillées

  • Dans l’article lié, il y a cette phrase : https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    « Si une proposition est démontrable, alors elle admet aussi une preuve à divulgation nulle de connaissance » — ça me retourne le cerveau
    Et l’autre idée, selon laquelle remplacer les bits aléatoires par des bits pseudo-aléatoires dans un algorithme probabiliste donnerait un algorithme déterministe efficace pour le même problème, est tout aussi hallucinante
    L’IA est elle aussi un calcul probabiliste, donc si j’ai bien compris, cela voudrait dire qu’on pourrait réduire de plusieurs ordres de grandeur la complexité des modèles actuels. Si c’est une confusion de débutant, j’aimerais qu’on me corrige

    • Je ne sais pas exactement ce que cela veut dire, mais en tout cas cela ne veut pas dire ça. L’IA utilise déjà du pseudo-aléatoire et elle est déterministe
      Il existe des exceptions, comme certaines puces accélératrices d’IA exotiques qui utilisent du calcul analogique pour gagner en efficacité
    • Malheureusement non. D’abord, ce résultat s’applique aux problèmes de décision, pas aux problèmes de recherche
      Ensuite, l’algorithme déterministe construit est bien moins efficace que l’algorithme randomisé. Il reste simplement dans la même classe de complexité sous des hypothèses faibles

  • J’ai aimé ce passage de l’article : « Les applications ne sont pas la motivation, mais même dans la recherche fondamentale on sait qu’elles peuvent apparaître. Pensez à Alan Turing. Il a écrit un article de logique mathématique sur l’Entscheidungsproblem dans une revue peu connue. Les applications n’étaient pas sa motivation »
    Cela rappelle l’anecdote de l’assiette de Feynman. Une réaction légère à quelque chose vu au restaurant universitaire a fini par mener au prix Nobel
    Plus largement, l’idée générale est que le monde universitaire moderne tend justement à réprimer ce type d’exploration guidée par la curiosité

  • Selon l’ACM, Avi Wigderson a été choisi comme lauréat du 2023 ACM A.M. Turing Award pour ses contributions fondamentales à la théorie du calcul, notamment pour avoir remodelé la compréhension du rôle du hasard dans le calcul, ainsi que pour son leadership intellectuel sur plusieurs décennies en informatique théorique
    Wigderson est Herbert H. Maass Professor au département de mathématiques de l’Institute for Advanced Study à Princeton, dans le New Jersey, et a joué un rôle central en théorie de la complexité, algorithmes et optimisation, hasard et cryptographie, calcul parallèle et distribué, combinatoire, théorie des graphes, ainsi que dans les liens entre informatique théorique et mathématiques/sciences
    Il a aussi reçu le prix Abel en 2021, ce qui constitue une combinaison assez rare des plus hautes distinctions en mathématiques théoriques/abstraites et en informatique

    • Le recoupement entre informatique théorique et mathématiques est bien plus important que la plupart des gens ne l’imaginent
      Par exemple, si l’on regarde la liste des cours d’informatique théorique du MIT https://catalog.mit.edu/subjects/6/, on peut voir combien de cours sont co-inscrits avec le cours 18, qui correspond aux mathématiques
    • Techniquement, la plus haute distinction en mathématiques est la médaille Fields
      Cela dit, je ne suis pas vraiment en position d’en juger

  • J’aimerais des recommandations de ressources, des plus accessibles aux plus avancées, pour étudier le thème probabilités / hasard et calcul
    Google me renvoie vers « Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis » d’Eli Upfal et Michael Mitzenmacher, mais j’ai du mal à trouver de bons livres, articles ou vidéos vraiment adaptés aux débutants