Michael Ezra Saks est un mathématicien et informaticien théoricien américain. Il travaille en théorie de la complexité, combinatoire et théorie des graphes.
Biographie
Michael Saks a obtenu un Ph. D. en 1980 au Massachusetts Institute of Technology sous la supervision de (). 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 . — Une première version de l'article, avec le même titre, a été présentée au ACM symposium on Theory of computing (STOC) de 1993 .. 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 topologieLaudatio prix Gödel 2004. Zaharoglou était en 1993 élève de Saks à l'université de Californie à San Diego.
Recherche 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 temps-mémoire. 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..
Un autre article, de 2008., 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, processeurs sont affectés à des bits d'entrée locaux . 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 , de calculer la valeur pour une fonction donnée. Les auteurs montrent qu'un protocole proposé par Gallager. est optimal, par une réduction depuis un arbre de décision généralisé avec bruit, et produit une minoration en sur la profondeur de l'arbre qui apprend les données en entrée.
Un article de 2003, avec Beame et al.., contient la première minoration du compromis espace temps pour le calcul randomisé de problèmes de décision.
Responsabilités scientifiques 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.
Notes et références
Liens externes Page personnelle à l'université Rutgers.
Catégorie:Informaticien américain Catégorie:Mathématicien américain du XXe siècle Catégorie:Professeur à l'université Rutgers Catégorie:Lauréat du prix Gödel Catégorie:Étudiant du Massachusetts Institute of Technology