Michael Saks

Michael Saks a obtenu un Ph. D. en 1980 au Massachusetts Institute of Technology sous la supervision de Daniel J. Kleitman (en) (« Duality Properties of Finite Set Systems »)[1]. Il est « distinguished professor » au département de mathématiques de Rutgers University.

En 2004, il est lauréat du prix Gödel, en même temps que Maurice Herlihy, Nir Shavit et Fotios Zaharoglou; l'article récompensé est son travail avec Zaharoglou: Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge [2]. Ce prix récompense leur découverte du rôle de la topologie dans le calcul distribué : elle permet de traiter la question de l'existence de protocoles pour certains problèmes en réduisant leur nature dynamique à un problème de topologie[3]. Zaharoglou était en 1993 élève de Saks à l'université de Californie à San Diego.

Michael Saks travaille sur des problèmes de théorie de la complexité, combinatoire et théorie des graphes. Il est notamment auteur ou coauteur de plusieurs résultats sur des bornes inférieures à la complexité de certains problèmes en théorie des ordres, algorithmique randomisée, et compromis espace temps (en). Voici trois exemples.

Dès 1984, un article avec Jeff Kahn porte sur l'existence d'une borne inférieure précise en théorie de l’information pour le problème du tri de données d'un poset[4].

Un autre article, de 2008[5], donne la première minoration super-linéaire pour le problème de la diffusion avec bruit « noisy broadcast problem » : Dans ce modèle de diffusion avec bruit, ${\displaystyle n+1}$ processeurs ${\displaystyle P_{0},P_{1},\ldots ,P_{n}}$ sont affectés à des bits d'entrée locaux ${\displaystyle x_{i}}$. Chaque processeur peut effectuer une diffusion avec bruit vers tous les autres processeurs, où les bits reçus peuvent avoir été inversés avec une certaine probabilité fixe. Le problème consiste, pour le processeur ${\displaystyle P_{0}}$, de calculer la valeur ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$ pour une fonction ${\displaystyle f}$ donnée. Les auteurs montrent qu'un protocole proposé par Gallager[6] est optimal, par une réduction depuis un arbre de décision généralisé avec bruit, et produit une minoration en ${\displaystyle \Omega (n\log(n))}$ sur la profondeur de l'arbre qui apprend les données en entrée.

Un article de 2003, avec Beame et al.[7], contient la première minoration du compromis espace temps pour le calcul randomisé de problèmes de décision.

Saks est ou a été membre des comités éditoriaux de diverses revues scientifiques, parmi lesquelles Combinatorica, Journal of Graph Theory, Discrete Applied Mathematics, Journal of the ACM, SIAM Journal on Computing, SIAM Journal on Discrete Mathematics. Il est membre du comité exécutif du « Center for Computational Intractability ». Il a été président du comité de programme de la conférence IEEE 2014 de « Computational Complexity ».

À l'université Rutgers, il préside le « Honors Committee » du département de mathématiques.

• Page personnelle à l'université Rutgers.
• Ressources relatives à la recherche :
  • (en) Digital Bibliography & Library Project
  • (en) Mathematics Genealogy Project
  • (en) ORCID
• Notices d'autorité :

  • Fichier d’autorité international virtuel
  • International Standard Name Identifier
  • Bibliothèque du Congrès
  • WorldCat

• Portail de l'informatique théorique
• Portail des mathématiques