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.
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, 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[6] 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.[7], 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.
↑Michael E. Saks et Fotios Zaharoglou, « Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge », SIAM Journal on Computing, vol. 29, no 5, , p. 1449-1483 (DOI10.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-110DOI10.1145/167088.167122.
↑Jeff Kahn et Michael Saks, « Every poset has a good comparison », Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84, , p. 299-301 (ISBN0897911334, DOI10.1145/800057.808694).
↑Navin Goyal, Guy Kindler et Michael E. Saks, « Lower Bounds for the Noisy Broadcast Problem », SIAM J. Comput, vol. 37, no 6, , p. 1806-1841.
↑R. G. Gallager, « Finding parity in simple broadcast networks », IEEE Transactions on Information Theory, vol. 34, , p. 176–180 (DOI10.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, no 2, , p. 154-195 (DOI10.1145/636865.636867).