Michael Sipser

Last updated
Michael Sipser
MIT-Science Sipser Michael.jpg
Born
Michael Fredric Sipser

(1954-09-17) September 17, 1954 (age 69)
Brooklyn, New York
Nationality American
Alma mater
Awards
Scientific career
Fields
Institutions MIT
Thesis Nondeterminism and the Size of Two-Way Finite Automata (1980)
Doctoral advisor Manuel Blum
Doctoral students
Website math.mit.edu/~sipser/

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 was the dean of science at the Massachusetts Institute of Technology.

Contents

Biography

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 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. [3] He served as Dean until 2020, when he was followed by Nergis Mavalvala. [4] He is a fellow of the American Academy of Arts and Sciences. [5] 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." [6] He was elected as an ACM Fellow in 2017. [7]

Scientific career

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. [8] Their result was later improved to be an exponential lower bound by Andrew Yao and Johan Håstad. [9]

In an early derandomization theorem, Sipser showed that BPP is contained in the polynomial hierarchy, [10] 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. [11] He and his PhD student Daniel Spielman introduced expander codes, an application of expander graphs. [12] With fellow graduate student David Lichtenstein, Sipser proved that Go is PSPACE hard. [13]

In quantum computation theory, he introduced the adiabatic algorithm jointly with Edward Farhi, Jeffrey Goldstone, and Samuel Gutmann. [14]

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. [15]

Notable books

Sipser is the author of Introduction to the Theory of Computation , [16] a textbook for theoretical computer science.

Personal life

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. [1]

Related Research Articles

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

<span class="mw-page-title-main">Quantum computing</span> Technology that uses quantum mechanics

A quantum computer is a computer that takes advantage of quantum mechanical phenomena.

<span class="mw-page-title-main">Stephen Cook</span> American-Canadian computer scientist, contributor to complexity theory

Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.

<span class="mw-page-title-main">Leonard Adleman</span> American computer scientist

Leonard Adleman is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award. He is also known for the creation of the field of DNA computing.

<span class="mw-page-title-main">Richard M. Karp</span> American mathematician

Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

<span class="mw-page-title-main">Manuel Blum</span> Venezuelan computer scientist

Manuel Blum is a Venezuelan born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output are random variables.

In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

<span class="mw-page-title-main">PH (complexity)</span> Class in computational complexity theory

In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:

In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system in which the verifier's coin tosses are constrained to be public. Goldwasser & Sipser (1986) proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins.

<span class="mw-page-title-main">Russell Impagliazzo</span> American computer scientist

Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.

In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that bounded-error probabilistic polynomial (BPP) time is contained in the polynomial time hierarchy, and more specifically Σ2 ∩ Π2.

Jeffrey Goldstone is a British theoretical physicist and an emeritus physics faculty member at the MIT Center for Theoretical Physics.

Umesh Virkumar Vazirani is an Indian–American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.

Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to perform calculations and is closely related to quantum annealing.

Daniel Alan Spielman has been a professor of applied mathematics and computer science at Yale University since 2006. As of 2018, he is the Sterling Professor of Computer Science at Yale. He is also the Co-Director of the Yale Institute for Network Science, since its founding, and chair of the newly established Department of Statistics and Data Science.

Richard Erwin Cleve is a Canadian professor of computer science at the David R. Cheriton School of Computer Science at the University of Waterloo, where he holds the Institute for Quantum Computing Chair in quantum computing, and an associate member of the Perimeter Institute for Theoretical Physics.

Lance Jeremy Fortnow is a computer scientist known for major results in computational complexity and interactive proof systems. As of January 2024, he was the Dean of the College of Computing at the Illinois Institute of Technology.

Edward Henry Farhi is a physicist working on quantum computation as a principal scientist at Google. In 2018 he retired from his position as the Cecil and Ida Green Professor of Physics at the Massachusetts Institute of Technology. He was the director of the Center for Theoretical Physics at MIT from 2004 until 2016. He made contributions to particle physics, general relativity and astroparticle physics before turning to his current interest, quantum computation.

Andrew MacGregor Childs is an American computer scientist and physicist known for his work on quantum computing. He is currently a professor in the department of computer science and Institute for Advanced Computer Studies at the University of Maryland. He also co-directs the Joint Center for Quantum Information and Computer Science, a partnership between the University of Maryland and the National Institute of Standards and Technology.

References

  1. 1 2 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
  2. ↑ Michael Sipser at the Mathematics Genealogy Project
  3. ↑ MIT Mathematics | People Directory Archived 2008-12-18 at the Wayback Machine
  4. ↑ "School of Science | MIT History" . Retrieved 2020-08-25.
  5. ↑ "Membership". American Academy of Arts and Sciences. Retrieved 23 September 2014.
  6. ↑ 2016 Class of the Fellows of the AMS, American Mathematical Society , retrieved 2015-11-16.
  7. ↑ ACM Recognizes 2017 Fellows for Making Transformative Contributions and Advancing Technology in the Digital Age, Association for Computing Machinery, December 11, 2017, retrieved 2017-11-13
  8. ↑ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/BF01744431. MR   0738749. S2CID   14677270.
  9. ↑ "Research Vignette: Hard Problems All The Way Up | Simons Institute for the Theory of Computing". simons.berkeley.edu. 30 July 2015. Retrieved 2015-09-17.
  10. ↑ Sipser, Michael (1983). "A complexity theoretic approach to randomness". Proceedings of the 15th ACM Symposium on Theory of Computing.
  11. ↑ Sipser, Michael (1986). "Expanders, randomness, or time versus space". Structure in Complexity Theory: Proceedings of the Conference held at the University of California, Berkeley, June 2-5, 1986. Lecture Notes in Computer Science. Vol. 223. pp. 325–329. doi:10.1007/3-540-16486-3_108. ISBN   978-3-540-16486-9.
  12. ↑ Sipser, Michael; Spielman, Daniel (1996). "Expander Codes" (PDF). IEEE Transactions on Information Theory. 42 (6): 1710–1722. doi:10.1109/18.556667.
  13. ↑ Lichtenstein, David; Sipser, Michael (1980-04-01). "GO Is Polynomial-Space Hard". J. ACM. 27 (2): 393–401. doi: 10.1145/322186.322201 . ISSN   0004-5411. S2CID   29498352.
  14. ↑ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam; Sipser, Michael (2000-01-28). "Quantum Computation by Adiabatic Evolution". arXiv: quant-ph/0001106 .
  15. ↑ Pavlus, John (2012-01-01). "Machines of the Infinite". Scientific American. 307 (3): 66–71. Bibcode:2012SciAm.307c..66P. doi:10.1038/scientificamerican0912-66. PMID   22928263.
  16. ↑ Sipser, Michael (2012-06-27). Introduction to the Theory of Computation (3 ed.). Cengage Learning. ISBN   978-1133187790.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.