Michael Saks is a mathematician known for his contributions to computational complexity theory, a field that explores the resources required to solve problems using algorithms. He has worked on topics such as the complexity of Boolean functions, lower bounds, and the theoretical underpinnings of various computational models. Saks has published numerous research papers and has had a significant influence in the area of theoretical computer science.
Articles by others on the same topic
Michael Saks coauthored Every decision tree has an influential variable by Ryan O'Donnell and others. The paper relates the variance of a Boolean function to coordinate influences and the probabilities with which a decision algorithm examines those coordinates. This turns a statement about an algorithm's observations into a structural statement about its input variables.[ref]