Michael Ezra Saks is an American mathematician. He is currently the Department Chair of the Mathematics Department at Rutgers University (2017–) and from 2006 until 2010 was director of the Mathematics Graduate Program at
Rutgers University. Saks received his Ph.D. from the
Massachusetts Institute of Technology in 1980 after completing his dissertation titled Duality Properties of Finite Set Systems[1] under his advisor
Daniel J. Kleitman.
A list of his publications and collaborations may be found at
DBLP.[2]
In 1984, Saks and Jeff Kahn showed that there exist a tight information-theoretical lower bound for sorting under
partially ordered information up to a multiplicative constant.[5]
In
[1] the first super-linear lower bound for the
noisy broadcast problem was proved. In a noisy broadcast model, processors are assigned a local input bit . Each processor may perform a noisy broadcast to all other processors where the received bits may be independently flipped with a fixed probability. The problem is for processor to determine for some function . Saks et al. showed that an existing protocol by Gallager was indeed optimal by a reduction from a generalized noisy
decision tree and produced a lower bound on the depth of the tree that learns the input.[6]
In 2003, P. Beame, Saks, X. Sun, and E. Vee published the first time–space lower bound trade-off for randomized computation of decision problems was proved.[7]
Positions
Saks holds positions in the following journal editorial boards:
Fredman, M.; Saks, M. (1989-02-01). "The cell probe complexity of dynamic data structures". Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. New York, NY, USA: Association for Computing Machinery. pp. 345–354.
doi:10.1145/73007.73040.
ISBN978-0-89791-307-2.
S2CID13470414.
Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R.; Saks, Michael; Wright, Andrew (2006-05-01).
"Competitive auctions". Games and Economic Behavior. Mini Special Issue: Electronic Market Design. 55 (2): 242–269.
doi:
10.1016/j.geb.2006.02.003.
ISSN0899-8256.
^Gallager, R. G. (1988). "Finding parity in simple broadcast networks". IEEE Transactions on Information Theory. 34 (2): 176–180.
CiteSeerX10.1.1.422.3311.
doi:
10.1109/18.2626.