View source for Michael Saks (mathematician)

{{short description|American mathematician}}
'''Michael Ezra Saks''' is an American mathematician. He is currently the Department Chair of the Mathematics Department at Rutgers University (2017–) and from 2006 until 2010 was 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 titled ''Duality Properties of Finite Set Systems''<ref name="thesis">{{cite thesis |last1=Saks |first1=Michael Ezra |date=1980 |title=Duality Properties of Finite Set Systems |degree=Ph.D. |publisher=[[Massachusetts Institute of Technology]] |oclc=7447661}}</ref> under his advisor [[Daniel J. Kleitman]].

A list of his publications and collaborations may be found at [[DBLP]].<ref>{{DBLP |name=Michael E. Saks}}</ref>

In 2016 he became a [[Fellow of the Association for Computing Machinery]].<ref>{{citation|title=ACM Recognizes New Fellows|journal=[[Communications of the ACM]]|date=March 2017|volume=60|issue=3|page=23|doi=10.1145/3039921|last1=Cacm Staff|s2cid=31701275}}.</ref><ref>{{Cite web|url=https://awards.acm.org/fellows/award-winners|title=Recipients|website=awards.acm.org|language=en|access-date=2018-07-01}}</ref>

==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 1984, Saks and [[Jeff Kahn (mathematician)|Jeff Kahn]] showed that there exist a tight information-theoretical lower bound for sorting under [[partially ordered]] information up to a multiplicative constant.<ref>{{Cite book | doi = 10.1145/800057.808694| chapter = Every poset has a good comparison| title = Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84| pages = 299| year = 1984| last1 = Kahn | first1 = J. | last2 = Saks | first2 = M. | isbn = 978-0897911337| s2cid = 17374296}}</ref>

In [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.5448&rep=rep1&type=pdf] the first super-linear lower bound for the [[noisy broadcast problem]] was proved. In a noisy broadcast model, <math>n+1</math> processors <math>P_0,P_1,\ldots,P_n</math> are assigned a local input bit <math>x_i</math>. 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 <math>P_0</math> to determine <math>f(x_1,x_2,\ldots,x_n)</math> for some function <math>f</math>. 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 <math>\Omega(n\log(n))</math> lower bound on the depth of the tree that learns the input.<ref>{{cite journal |first=R. G. |last=Gallager |title=Finding parity in simple broadcast networks |journal=IEEE Transactions on Information Theory |volume=34 |issue= 2|pages=176–180 |year=1988 |doi= 10.1109/18.2626|citeseerx=10.1.1.422.3311 }}</ref>

In 2003, P. Beame, Saks, X. Sun, and E. Vee published the first time–space lower bound trade-off for randomized computation of decision problems was proved.<ref>{{Cite journal | doi = 10.1145/636865.636867| title = Time–space trade-off lower bounds for randomized computation of decision problems| journal = Journal of the ACM| volume = 50| issue = 2| pages = 154| year = 2003| last1 = Beame | first1 = P. | last2 = Saks | first2 = M. | last3 = Sun | first3 = X. | last4 = Vee | first4 = E. | citeseerx = 10.1.1.16.8696| s2cid = 9459178}}</ref>

==Positions==
Saks holds positions in the following journal editorial boards:

* [[SIAM Journal on Computing]], Associate Editor
* [[Combinatorica]], Editorial Board member
* [[Journal of Graph Theory]], Editorial Board member
* [[Discrete Applied Mathematics]], Editorial Board member

==Selected publications==
* {{Cite journal |last1=Borodin |first1=Allan |last2=Linial |first2=Nathan |last3=Saks |first3=Michael E. |date=1992-10-01 |title=An optimal on-line algorithm for metrical task system |journal=Journal of the ACM |volume=39 |issue=4 |pages=745–763 |doi=10.1145/146585.146588 |s2cid=18783826 |issn=0004-5411|doi-access=free }}
* {{Cite book |last1=Fredman |first1=M. |last2=Saks |first2=M. |title=Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 |chapter=The cell probe complexity of dynamic data structures |date=1989-02-01 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=345–354 |doi=10.1145/73007.73040 |isbn=978-0-89791-307-2|s2cid=13470414 |doi-access=free }}
* {{Cite journal |last1=Paturi |first1=Ramamohan |last2=Pudlák |first2=Pavel |last3=Saks |first3=Michael E. |last4=Zane |first4=Francis |date=2005-05-01 |title=An improved exponential-time algorithm for k-SAT |url=https://doi.org/10.1145/1066100.1066101 |journal=Journal of the ACM |volume=52 |issue=3 |pages=337–364 |doi=10.1145/1066100.1066101 |issn=0004-5411}}
* {{Cite journal |last1=Goldberg |first1=Andrew V. |last2=Hartline |first2=Jason D. |last3=Karlin |first3=Anna R. |last4=Saks |first4=Michael |last5=Wright |first5=Andrew |date=2006-05-01 |title=Competitive auctions |url=https://www.sciencedirect.com/science/article/pii/S0899825606000303 |journal=Games and Economic Behavior |series=Mini Special Issue: Electronic Market Design |language=en |volume=55 |issue=2 |pages=242–269 |doi=10.1016/j.geb.2006.02.003 |issn=0899-8256}}
* {{Cite journal |last1=Saks |first1=Michael |last2=Zaharoglou |first2=Fotios |date=2000-01-01 |title=Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge |url=https://epubs.siam.org/doi/10.1137/S0097539796307698 |journal=SIAM Journal on Computing |volume=29 |issue=5 |pages=1449–1483 |doi=10.1137/S0097539796307698 |issn=0097-5397}}
* {{Cite book |last1=Saks |first1=Michael |last2=Wigderson |first2=Avi |title=27th Annual Symposium on Foundations of Computer Science (SFCS 1986) |chapter=Probabilistic Boolean decision trees and the complexity of evaluating game trees |date=October 1986 |chapter-url=https://ieeexplore.ieee.org/document/4568192 |pages=29–38 |doi=10.1109/SFCS.1986.44|isbn=0-8186-0740-8 |s2cid=6130392 }}
* {{Cite book |last1=Saks |first1=Michael |last2=Yu |first2=Lan |title=Proceedings of the 6th ACM conference on Electronic commerce |chapter=Weak monotonicity suffices for truthfulness on convex domains |date=2005-06-05 |chapter-url=https://doi.org/10.1145/1064009.1064040 |series=EC '05 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=286–293 |doi=10.1145/1064009.1064040 |isbn=978-1-59593-049-1|s2cid=2135397 }}

==References==
<!--- See [[Wikipedia:Footnotes]] on how to create references using <ref></ref> tags which will then appear here automatically -->
{{Reflist}}

==External links==
* {{MathGenealogy |title=Michael Ezra Saks}}

{{Gödel Prize laureates}}

{{Authority control}}

{{DEFAULTSORT:Saks, Michael}}
[[Category:Living people]]
[[Category:Rutgers University faculty]]
[[Category:Gödel Prize laureates]]
[[Category:Massachusetts Institute of Technology School of Science alumni]]
[[Category:American theoretical computer scientists]]
[[Category:Year of birth missing (living people)]]
[[Category:Combinatorialists]]