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 the first super-linear lower bound for the noisy broadcast problem was proved.