Michael Sipser
Michael Sipser  

Born  Michael Fredric Sipser September 17, 1954 
Nationality  American 
Alma mater  
Awards 

Scientific career  
Fields  
Institutions  MIT 
Thesis  Nondeterminism and the Size of TwoWay Finite Automata (1980) 
Doctoral advisor  Manuel Blum 
Doctoral students  
Website  http://math.mit.edu/directory/profile.php?pid=251 
Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of Applied Mathematics and Dean of Science at the Massachusetts Institute of Technology.
Contents
Biography[edit]
Sipser was born and raised in Brooklyn, New York and moved to Oswego, New York when he was 12 years old. He earned his BA in mathematics from Cornell University in 1974 and his PhD in engineering from the University of California at Berkeley in 1980 under the direction of Manuel Blum.^{[1]}^{[2]}
He joined MIT's Laboratory for Computer Science as a research associate in 1979 and then was a Research Staff Member at IBM Research in San Jose. In 1980, he joined the MIT faculty. He spent the 19851986 academic year on the faculty of the University of California at Berkeley and then returned to MIT. From 2004 until 2014, he served as head of the MIT Mathematics department. He was appointed Dean of the MIT School of Science in 2014.^{[3]} He is a fellow of the American Academy of Arts and Sciences.^{[4]} In 2015 he was elected as a fellow of the American Mathematical Society "for contributions to complexity theory and for leadership and service to the mathematical community."^{[5]} He was elected as an ACM Fellow in 2017.^{[6]}
Scientific career[edit]
Sipser specializes in algorithms and complexity theory, specifically efficient error correcting codes, interactive proof systems, randomness, quantum computation, and establishing the inherent computational difficulty of problems. He introduced the method of probabilistic restriction for proving superpolynomial lower bounds on circuit complexity in a paper joint with Merrick Furst and James B. Saxe.^{[7]} Their result was later improved to be an exponential lower bound by Andrew Yao and Johan Håstad.^{[8]}
In an early derandomization theorem, Sipser showed that BPP is contained in the polynomial hierarchy,^{[9]} subsequently improved by Peter Gács and Clemens Lautemann to form what is now known as the SipserGàcsLautemann theorem. Sipser also established a connection between expander graphs and derandomization.^{[10]} He and his PhD student Daniel Spielman introduced expander codes, an application of expander graphs.^{[11]} With fellow graduate student David Lichtenstein, Sipser proved that Go is PSPACE hard.^{[12]}
In quantum computation theory, he introduced the adiabatic algorithm jointly with Edward Farhi, Jeffrey Goldstone, and Samuel Gutmann.^{[13]}
Sipser has long been interested in the P versus NP problem. In 1975, he wagered an ounce of gold with Leonard Adleman that the problem would be solved with a proof that P≠NP by the end of the 20th century. Sipser sent Adleman an American gold eagle coin in 2000 because the problem remained (and remains) unsolved.^{[14]}
Notable books[edit]
Sipser is the author of Introduction to the Theory of Computation,^{[15]} a textbook for theoretical computer science.
Personal life[edit]
Sipser lives in Cambridge, Massachusetts with his wife, Ina, and has two children: a daughter, Rachel, who graduated from New York University, and a younger son, Aaron, who is an undergraduate at MIT.^{[1]}
References[edit]
 ^ ^{a} ^{b} Trafton, Anne, "Michael Sipser named dean of the School of Science: Sipser has served as interim dean since Marc Kastner’s departure", MIT News Office, June 5, 2014
 ^ Michael Sipser at the Mathematics Genealogy Project
 ^ MIT Mathematics  People Directory Archived 20081218 at the Wayback Machine
 ^ "Membership". American Academy of Arts and Sciences. Retrieved 23 September 2014.
 ^ 2016 Class of the Fellows of the AMS, American Mathematical Society, retrieved 20151116.
 ^ ACM Recognizes 2017 Fellows for Making Transformative Contributions and Advancing Technology in the Digital Age, Association for Computing Machinery, December 11, 2017, retrieved 20171113
 ^ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parity, circuits, and the polynomialtime hierarchy". Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/BF01744431. MR 0738749.
 ^ "Research Vignette: Hard Problems All The Way Up  Simons Institute for the Theory of Computing". simons.berkeley.edu. Retrieved 20150917.
 ^ Sipser, Michael (1983). "A complexity theoretic approach to randomness". Proceedings of the 15th ACM Symposium on Theory of Computing.
 ^ Sipser, Michael (1986). "Expanders, Randomness, or Time versus Space". Proceedings of the Conference on Structure in Complexity.
 ^ Sipser, Michael; Spielman, Daniel (1996). "Expander Codes" (PDF). IEEE Transactions on Information Theory. 42 (6): 1710–1722. doi:10.1109/18.556667.
 ^ Lichtenstein, David; Sipser, Michael (19800401). "GO Is PolynomialSpace Hard". J. ACM. 27 (2): 393–401. doi:10.1145/322186.322201. ISSN 00045411.
 ^ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam; Sipser, Michael (20000128). "Quantum Computation by Adiabatic Evolution". arXiv:quantph/0001106.
 ^ Pavlus, John (20120101). "Machines of the Infinite". Scientific American. 307 (3): 66–71. Bibcode:2012SciAm.307c..66P. doi:10.1038/scientificamerican091266.
 ^ Sipser, Michael. Introduction to the Theory of Computation (3 ed.). Cengage Learning. ISBN 9781133187790.
External links[edit]
 1954 births
 Living people
 20thcentury mathematicians
 21stcentury mathematicians
 University of California, Berkeley alumni
 Massachusetts Institute of Technology faculty
 Theoretical computer scientists
 Fellows of the American Mathematical Society
 Fellows of the American Academy of Arts and Sciences
 Fellows of the Association for Computing Machinery
 Computer science educators
 Quantum information scientists