Michael Saks (mathematician)

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 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, n + 1 processors P 0 , P 1 , … , P n are assigned a local input bit 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 P 0 to determine f ( x 1 , x 2 , … , x n ) 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 Ω ( n log ⁡ ( n ) ) lower bound on the depth of the tree that learns the input.

In Beame et al. (2003) the first time-space lower bound trade-off for randomized computation of decision problems was proved.

Positions

Saks holds positions in the following journal editorial boards: