Michael Saks

Biographie
Naissance	Avril 1956
Nationalité	américaine
Formation	Massachusetts Institute of Technology
Activités	Mathématicien, professeur d'université, informaticien

Autres informations
A travaillé pour	Université Rutgers
Directeur de thèse	Daniel Kleitman
Distinctions	Prix Gödel (2004) ACM Fellow (2016)

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 modifier

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.

Recherche modifier

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, $n+1$ processeurs $P_{0},P_{1},\ldots ,P_{n}$ sont affectés à des bits d'entrée locaux $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 $P_{0}$ , de calculer la valeur $f(x_{1},x_{2},\ldots ,x_{n})$ pour une fonction $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 $\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.

Responsabilités scientifiques modifier

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 modifier

↑ (en) « Michael Ezra Saks », sur le site du Mathematics Genealogy Project
↑ Michael E. Saks et Fotios Zaharoglou, « Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge », SIAM Journal on Computing, vol. 29, n^o 5,‎ 2000, p. 1449-1483 (DOI 10.1137/S0097539796307698). — 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 p. 101-110 DOI 10.1145/167088.167122.
↑ Laudatio prix Gödel 2004
↑ Jeff Kahn et Michael Saks, « Every poset has a good comparison », Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84,‎ 1984, p. 299-301 (ISBN 0897911334, DOI 10.1145/800057.808694).
↑ Navin Goyal, Guy Kindler et Michael E. Saks, « Lower Bounds for the Noisy Broadcast Problem », SIAM J. Comput, vol. 37, n^o 6,‎ 2008, p. 1806-1841.
↑ R. G. Gallager, « Finding parity in simple broadcast networks », IEEE Transactions on Information Theory, vol. 34,‎ 1988, p. 176–180 (DOI 10.1109/18.2626).
↑ Paul Beame, Michael Saks, Xiaodong Sun et Erik Vee, « Time-space trade-off lower bounds for randomized computation of decision problems », Journal of the ACM, vol. 50, n^o 2,‎ 2003, p. 154-195 (DOI 10.1145/636865.636867).

(de)/(en) Cet article est partiellement ou en totalité issu des articles intitulés en allemand « Michael Saks » (voir la liste des auteurs) et en anglais « Michael Saks » (voir la liste des auteurs).

Liens externes modifier

Page personnelle à l'université Rutgers.
Ressources relatives à la recherche :
Notices d'autorité :
- VIAF
- ISNI
- LCCN
- WorldCat

[1] (en) « Michael Ezra Saks », sur le site du Mathematics Genealogy Project

[2] Michael E. Saks et Fotios Zaharoglou, « Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge », SIAM Journal on Computing, vol. 29, n^o 5,‎ 2000, p. 1449-1483 (DOI 10.1137/S0097539796307698). — 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 p. 101-110 DOI 10.1145/167088.167122.

[3] Laudatio prix Gödel 2004

[4] Jeff Kahn et Michael Saks, « Every poset has a good comparison », Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84,‎ 1984, p. 299-301 (ISBN 0897911334, DOI 10.1145/800057.808694).

[5] Navin Goyal, Guy Kindler et Michael E. Saks, « Lower Bounds for the Noisy Broadcast Problem », SIAM J. Comput, vol. 37, n^o 6,‎ 2008, p. 1806-1841.

[6] R. G. Gallager, « Finding parity in simple broadcast networks », IEEE Transactions on Information Theory, vol. 34,‎ 1988, p. 176–180 (DOI 10.1109/18.2626).

[7] Paul Beame, Michael Saks, Xiaodong Sun et Erik Vee, « Time-space trade-off lower bounds for randomized computation of decision problems », Journal of the ACM, vol. 50, n^o 2,‎ 2003, p. 154-195 (DOI 10.1145/636865.636867).

[1]

[2]

[3]

[4]

[5]

[6]

[7]