- Michael Saks (mathematician)
Michael Ezra Saks is a professor and was (2006–2010) 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 entitled Duality Properties of Finite Set Systems  under his advisor Daniel J. Kleitman.
A list of his publications and collaborations may be found at.
In, it was shown there exist a tight information-theoretical lower bound for sorting under partially ordered information up to a multiplicative constant.
In, the first super-linear lower bound for the noisy broadcast problem was proved. In a noisy broadcast model, n + 1 processors P0,P1,...,Pn are assigned a local input bit xi. 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 P0 to determined f(x1,x2,...xn) for some function f. 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 Ω(nlog(n)) lower bound on the depth of the tree that learns the input.
In, the first time-space lower bound trade-off for randomized computation of decision problems was proved.
Saks holds positions in the following journal editorial boards:
- SIAM J. on Computing, Associate Editor
- Combinatorica, Editorial Board member
- Journal of Graph Theory, Editorial Board member
- Discrete Applied Mathematics, Editorial Board member
- ^ http://en.scientificcommons.org/2859536
- ^ http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/s/Saks:Michael_E=.html
- ^ http://portal.acm.org/citation.cfm?id=800057.808694
- ^ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.5448&rep=rep1&type=pdf
- ^ R. G. Gallager. Finding parity in simple broadcast networks. IEEE Transactions on Information Theory, 34:176--180, 1988.
- ^ http://portal.acm.org/citation.cfm?id=636865.636867
Gödel Prize laureates
Babai / Goldwasser / Micali / Moran / Rackoff (1993) · Håstad (1994) · Immerman / Szelepcsényi (1995) · Jerrum / Sinclair (1996) · Halpern / Moses (1997) · Toda (1998) · Shor (1999) · Vardi / Wolper (2000) · Arora / Feige / Goldwasser / Lund / Lovász / Motwani / Safra / Sudan / Szegedy (2001) · Sénizergues (2002) · Freund / Schapire (2003) · Herlihy / Saks / Shavit / Zaharoglou (2004) · Alon / Matias / Szegedy (2005) · Agrawal / Kayal / Saxena (2006) · Razborov / Rudich (2007) · Teng / Spielman (2008) · Reingold / Vadhan / Wigderson (2009) · Arora / Mitchell (2010) · Håstad (2011)
Wikimedia Foundation. 2010.