Michael Saks (mathematician)
Encyclopedia
Michael Ezra Saks is a professor and 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.
, combinatorics
, and graph theory
has contributed to the study of lower bounds in order theory
, randomized computation, and space-time tradeoff
.
In, it was shown there exist a tight information-theoretical lower bound for sorting under partially ordered information up to a multiplicative constant.
In, the first super-linear lower bound for the noisy broadcast problem was proved. In a noisy broadcast model,
processors 
are assigned a local input bit 
. 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 
to determined 
for some function 
. 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
lower bound on the depth of the tree that learns the input.
In, the first time-space lower bound trade-off for randomized computation of decision problems was proved.
Rutgers University
Rutgers, The State University of New Jersey , is the largest institution for higher education in New Jersey, United States. It was originally chartered as Queen's College in 1766. It is the eighth-oldest college in the United States and one of the nine Colonial colleges founded before the American...
. Saks received his Ph.D from the Massachusetts Institute of Technology
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
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.
Research
Saks research in computational complexity theoryComputational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, and graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
has contributed to the study of lower bounds in order theory
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, randomized computation, and space-time tradeoff
Space-time tradeoff
In computer science, a space–time or time–memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution...
.
In, it was shown there exist a tight information-theoretical lower bound for sorting under partially ordered information up to a multiplicative constant.
In, the first super-linear lower bound for the noisy broadcast problem was proved. In a noisy broadcast model,
processors are assigned a local input bit . 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 to determined for some function . Saks et al. showed that an existing protocol by Gallager was indeed optimal by a reduction from a generalized noisy decision treeDecision tree
A decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm. Decision trees are commonly used in operations research, specifically...
and produced a
lower bound on the depth of the tree that learns the input.In, the first time-space lower bound trade-off for randomized computation of decision problems was proved.
Other Positions
Saks holds positions in the following journal editorial boards:- SIAM J. on Computing, Associate Editor
- Combinatorica, Editorial Board member
- Journal of Graph Theory, Editorial Board member
- Discrete Applied Mathematics, Editorial Board member
External links
- http://www.genealogy.ams.org/id.php?id=6186&fChrono=1