Biography:Michael Saks (mathematician)

From HandWiki
Short description: American mathematician

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 2016 he became a Fellow of the Association for Computing Machinery.[3][4]

Research

Saks' research in computational complexity theory, combinatorics, and graph theory has contributed to the study of lower bounds in order theory, randomized computation, and space–time tradeoff.

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, [math]\displaystyle{ n+1 }[/math] processors [math]\displaystyle{ P_0,P_1,\ldots,P_n }[/math] are assigned a local input bit [math]\displaystyle{ x_i }[/math]. 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 [math]\displaystyle{ P_0 }[/math] to determine [math]\displaystyle{ f(x_1,x_2,\ldots,x_n) }[/math] for some function [math]\displaystyle{ f }[/math]. 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 [math]\displaystyle{ \Omega(n\log(n)) }[/math] 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:

Selected publications

References

  1. Saks, Michael Ezra (1980). Duality Properties of Finite Set Systems (Ph.D. thesis). Massachusetts Institute of Technology. OCLC 7447661.
  2. {{DBLP}} template missing ID and not present in Wikidata.
  3. Cacm Staff (March 2017), "ACM Recognizes New Fellows", Communications of the ACM 60 (3): 23, doi:10.1145/3039921 .
  4. "Recipients" (in en). https://awards.acm.org/fellows/award-winners. 
  5. Kahn, J.; Saks, M. (1984). "Every poset has a good comparison". Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84. pp. 299. doi:10.1145/800057.808694. ISBN 978-0897911337. 
  6. Gallager, R. G. (1988). "Finding parity in simple broadcast networks". IEEE Transactions on Information Theory 34 (2): 176–180. doi:10.1109/18.2626. 
  7. Beame, P.; Saks, M.; Sun, X.; Vee, E. (2003). "Time–space trade-off lower bounds for randomized computation of decision problems". Journal of the ACM 50 (2): 154. doi:10.1145/636865.636867. 

External links