Michael Saks (mathematician)

Michael Ezra Saks is an American mathematician. He 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 DBLP.

In 2017 he became a Fellow of the Association for Computing Machinery.

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 Kahn and Saks (1984) it was shown there exist a tight information-theoretical lower bound for sorting under partially ordered information up to a multiplicative constant.

In [1] the first super-linear lower bound for the noisy broadcast problem was proved. In a noisy broadcast model, ${\displaystyle n+1}$ processors ${\displaystyle P_{0},P_{1},\ldots ,P_{n}}$ are assigned a local input bit ${\displaystyle x_{i}}$. 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 ${\displaystyle P_{0}}$ to determine ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$ for some function ${\displaystyle 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 ${\displaystyle \Omega (n\log(n))}$ lower bound on the depth of the tree that learns the input.

...
Wikipedia