Michael Sipser

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.{{Cite web |date=2014-06-05 |title=Michael Sipser named dean of the School of Science |url=https://news.mit.edu/2014/michael-sipser-named-dean-school-science |access-date=2024-09-20 |website=MIT News {{!}} Massachusetts Institute of Technology |language=en}}{{MathGenealogy|64971}}

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 1985–1986 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 Interim Dean of the MIT School of Science in 2013 and Dean in 2014.[http://www-math.mit.edu/people/listing.php MIT Mathematics | People Directory] {{webarchive|url=https://web.archive.org/web/20081218183932/http://www-math.mit.edu/people/listing.php |date=2008-12-18 }} He served as Dean until 2020, when he was followed by Nergis Mavalvala.{{Cite web|title=School of Science {{!}} MIT History|url=https://libraries.mit.edu/mithistory/research/schools-and-departments/school-of-science/|access-date=2020-08-25|language=en-US}} He is a fellow of the American Academy of Arts and Sciences.{{Cite web|url = https://www.amacad.org/content/members/members.aspx|title = Membership|accessdate = 23 September 2014|website = American Academy of Arts and Sciences}} 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."{{citation|url=https://www.ams.org/profession/ams-fellows/new-fellows|title=2016 Class of the Fellows of the AMS|publisher=American Mathematical Society|accessdate=2015-11-16}}.

He was elected as an ACM Fellow in 2017.{{citation|url=https://www.acm.org/media-center/2017/december/fellows-2017|title=ACM Recognizes 2017 Fellows for Making Transformative Contributions and Advancing Technology in the Digital Age|publisher=Association for Computing Machinery|date=December 11, 2017|accessdate=2017-11-13}}

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 super-polynomial lower bounds on circuit complexity in a paper joint with Merrick Furst and James B. Saxe.{{cite journal | last1 = Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | doi = 10.1007/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984| s2cid = 14677270 }} Their result was later improved to be an exponential lower bound by Andrew Yao and Johan Håstad.{{Cite web|title = Research Vignette: Hard Problems All The Way Up {{!}} Simons Institute for the Theory of Computing|url = https://simons.berkeley.edu/news/research-vignette-Tan-Rossman-2015|website = simons.berkeley.edu|date = 30 July 2015|accessdate = 2015-09-17}}

In an early derandomization theorem, Sipser showed that BPP is contained in the polynomial hierarchy,{{Cite journal|title = A complexity theoretic approach to randomness|last = Sipser|first = Michael|date = 1983|journal = Proceedings of the 15th ACM Symposium on Theory of Computing}} subsequently improved by Peter Gács and Clemens Lautemann to form what is now known as the Sipser–Gács–Lautemann theorem. Sipser also established a connection between expander graphs and derandomization.{{Cite book|last = Sipser|first = Michael| title=Structure in Complexity Theory: Proceedings of the Conference held at the University of California, Berkeley, June 2–5, 1986 | chapter=Expanders, randomness, or time versus space |date = 1986|series = Lecture Notes in Computer Science|volume = 223|pages = 325–329|doi = 10.1007/3-540-16486-3_108|isbn = 978-3-540-16486-9}} He and his PhD student Daniel Spielman introduced expander codes, an application of expander graphs.{{Cite journal|url = http://www.cs.yale.edu/homes/spielman/PAPERS/expandersIT.pdf|title = Expander Codes|last1 = Sipser|first1 = Michael|date = 1996|journal = IEEE Transactions on Information Theory|doi = 10.1109/18.556667|last2 = Spielman|first2 = Daniel|issue = 6|volume = 42|pages = 1710–1722}} With fellow graduate student David Lichtenstein, Sipser proved that Go is PSPACE hard.{{Cite journal|title = GO Is Polynomial-Space Hard|journal = J. ACM|date = 1980-04-01|issn = 0004-5411|pages = 393–401|volume = 27|issue = 2|doi = 10.1145/322186.322201|first1 = David|last1 = Lichtenstein|first2 = Michael|last2 = Sipser|s2cid = 29498352|doi-access = free}}

In quantum computation theory, he introduced the adiabatic algorithm jointly with Edward Farhi, Jeffrey Goldstone, and Samuel Gutmann.{{cite arXiv|title = Quantum Computation by Adiabatic Evolution|eprint=quant-ph/0001106|date = 2000-01-28|first1 = Edward|last1 = Farhi|first2 = Jeffrey|last2 = Goldstone|first3 = Sam|last3 = Gutmann|first4 = Michael|last4 = Sipser}}

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.{{Cite journal|title = Machines of the Infinite|journal = Scientific American|date = 2012-01-01|volume = 307|issue = 3|doi = 10.1038/scientificamerican0912-66|pmid = 22928263|first = John|last = Pavlus|pages=66–71|bibcode = 2012SciAm.307c..66P}}

Sipser is the author of Introduction to the Theory of Computation,{{cite book|title=Introduction to the Theory of Computation|first=Michael|last=Sipser|publisher=Cengage Learning|isbn=978-1133187790|edition=3|date=2012-06-27}} a textbook for theoretical computer science.

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 graduated from MIT.

{{reflist|30em}}

• [http://www-math.mit.edu/~sipser/ Personal homepage at MIT]

{{authority control}}

{{DEFAULTSORT:Sipser, Michael}}

Category:1954 births

Category:Living people

Category:20th-century American mathematicians

Category:21st-century American mathematicians

Category:University of California, Berkeley alumni

Category:Massachusetts Institute of Technology School of Science faculty

Category:American theoretical computer scientists

Category:Fellows of the American Mathematical Society

Category:Fellows of the American Academy of Arts and Sciences

Category:2017 fellows of the Association for Computing Machinery

Category:American computer science educators

Category:American quantum information scientists

Category:Cornell University alumni

Category:20th-century American engineers

Category:21st-century American engineers