Fact-checked by Grok 2 weeks ago

Michael Sipser

Michael Sipser (born September 17, 1954) is an theoretical renowned for his pioneering contributions to , including work on interactive proof systems, derandomization, and expander graphs, as well as for authoring the seminal textbook Introduction to the . Born in , , Sipser earned a B.A. in from in 1974 and a Ph.D. from the in 1980, with a dissertation on nondeterminism and the size of two-way finite automata supervised by . He joined the () as a research associate in 1979 and became a faculty member in 1980, where he is the Donner Professor of and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL). Throughout his career, Sipser has held key administrative roles at , including chair of the Committee from 1998 to 2000, head of the Department of from 2004 to 2014, and dean of the School of Science from 2014 to 2020. His research has advanced foundational aspects of , such as lower bounds on complexity and the complexity of multi-prover interactive proofs, influencing areas like quantum computation and error-correcting codes. Sipser's textbook Introduction to the Theory of Computation, first published in 1996 and now in its third edition (2012), is a standard reference in , , and , widely used in undergraduate and graduate courses worldwide. He is recognized for excellence in teaching, having received the Graduate Student Council Teaching multiple times (1984, 1989, 1991), the School of Student Advising in 2003, and the Margaret MacVicar Fellowship in 2016. Sipser is a fellow of the American Academy of Arts and Sciences (elected 2009) and the (elected 2016), and he received the University of California, Berkeley Distinguished Alumni in 2015.

Early Life and Education

Childhood and Upbringing

Michael Sipser was born on September 17, 1954, in Brooklyn, New York. As a native New Yorker, he spent his early childhood in the urban setting of Brooklyn. At age 12, Sipser's family relocated to Oswego, New York, a small lakeside town. The change from city life to a quieter community provided new formative experiences during his pre-teen and teenage years. In Oswego, he attended Oswego High School, where he demonstrated strong academic aptitude. He graduated from the school in 1971.

Academic Training

Sipser earned a degree in from in 1974. Following his undergraduate studies, Sipser pursued graduate work at the , where he completed a in engineering in 1980. His doctoral dissertation, supervised by in the Department of and Computer Sciences, was titled Nondeterminism and the Size of Two-Way Finite Automata. This work examined foundational questions in and , exploring the resources required for nondeterministic computation models. During his , Sipser initiated research in . His early contributions laid groundwork for understanding nondeterminism's role in automata size and efficiency, influencing subsequent developments in .

Professional Career

Faculty Appointments

Following his from the in 1980, Sipser joined the (MIT) faculty that same year as an assistant professor of in the Department of Mathematics. He also served as a in MIT's Laboratory for Computer Science starting in 1979, prior to his formal faculty appointment. During his early career, Sipser had a brief stint as a research staff member at in 1980. He was promoted to in 1983 and to full professor in 1989. Later, he was appointed the Donner Professor of Mathematics, a position he continues to hold. Sipser has maintained a long-standing affiliation with MIT's and Laboratory (CSAIL), serving as a member since its in 2003 as the successor to the for .

Administrative Leadership

Michael Sipser served as Chair of the Committee at from 1998 to 2000, where he oversaw the program's direction during a period of growing emphasis on interdisciplinary computational approaches. His in this built on his expertise in , fostering collaborations between mathematics and departments. From 2004 to 2014, Sipser headed the MIT Department of Mathematics, guiding the department through expansions in faculty and research initiatives while maintaining its reputation for excellence in pure and . During his tenure, the department navigated significant institutional changes, including increased focus on computational theory and graduate program enhancements. Sipser was appointed interim dean of the MIT School of Science in December 2013 and confirmed as full dean in June 2014, a position he held until 2020. In this capacity, he launched key initiatives to support scientific research and education, including efforts to promote and interdisciplinary programs across the school's departments. He was succeeded by , effective September 1, 2020. Sipser co-chaired the MIT Ad Hoc Committee on Academic Freedom and Campus Expression (CAFCE), which was formed in 2024 to address issues of free speech, civility, and inclusion on campus by engaging faculty, staff, and students. The committee aimed to develop guidelines that balance academic freedom with respectful discourse, responding to contemporary challenges in higher education environments.

Research Contributions

Advances in Computational Complexity

In the late 1970s, Sipser, along with Merrick Furst and James Saxe, developed the probabilistic restriction method as a technique for establishing lower bounds on the size of bounded-depth circuits. This method involves randomly restricting the inputs to a circuit, which simplifies its structure while preserving the ability to compute specific functions, such as the , thereby demonstrating super-polynomial size requirements for constant-depth circuits. Their approach marked a significant advancement in by providing a probabilistic tool to handle the challenges of proving lower bounds in restricted models of computation. Sipser's work on randomized computation culminated in the Sipser–Gács–Lautemann theorem, established through collaborative efforts in 1983, which shows that bounded-error probabilistic polynomial time (BPP) is contained within the second level of the polynomial hierarchy, specifically \Sigma_2^p \cap \Pi_2^p. In his seminal paper, Sipser proved that BPP lies in the fourth level of the hierarchy using resource-bounded to construct hard functions that derandomize probabilistic algorithms. This result was refined by Péter Gács to the third level and by Clemens Lautemann to the second, providing evidence that randomness does not increase computational power beyond deterministic polynomial-time hierarchies. Sipser also made foundational contributions to interactive proof systems, particularly in understanding the role of randomness in verification protocols. In collaboration with , he demonstrated the equivalence between private-coin and public-coin interactive proofs, showing that any private-coin protocol can be simulated by a public-coin one with a increase in communication rounds, which facilitated subsequent breakthroughs in the field. This work laid groundwork for results like = , highlighting the power of randomized interaction in capturing -space computations. Additionally, Sipser co-proved that the game of Go is -hard by reducing quantified formulas via generalized geography to Go positions on an n \times n board, establishing the inherent computational difficulty of determining winners in such impartial games. These advances in have broader implications, including applications to quantum computation where randomized and interactive models inform the study of quantum proof systems.

Work in Related Fields

In the , Sipser co-developed expander codes, a class of asymptotically good linear error-correcting codes constructed from expander graphs, which enable efficient encoding and decoding while achieving rates close to the limit for certain error patterns. These codes, introduced in collaboration with Daniel A. Spielman, leverage the expansion properties of bipartite graphs to correct a constant fraction of errors in linear time, making them suitable for applications in and communication systems where computational efficiency is paramount. Sipser contributed to the foundational exploration of adiabatic quantum algorithms, co-authoring an early paper that proposed using adiabatic evolution to solve satisfiability problems by slowly varying a quantum system's Hamiltonian to maintain the ground state. This work, with Edward Farhi, Jeffrey Goldstone, and S. Gutmann, demonstrated that adiabatic quantum computation could potentially factorize numbers and solve optimization tasks, raising questions about the complexity classes achievable under this paradigm and its equivalence to standard quantum circuit models. Sipser's research on randomness in computation emphasized time-bounded variants of to define , showing that certain probabilistic algorithms could be derandomized using techniques. This approach has direct ties to , as it underpins the construction of pseudorandom generators secure against computational adversaries, influencing protocols for secure and schemes. His efforts overlap briefly with derandomization, illustrating how resource-bounded can simulate truly random sources in interactive proofs. Additionally, Sipser explored topological aspects of complexity problems by modeling decision problems as continuous objects in topological spaces, aiming to draw analogies between and geometric invariants to probe barriers in proving lower bounds. This perspective, outlined in his 1984 paper, suggested that topological obstructions might explain the intractability of certain problems, providing a novel lens for understanding separations in complexity classes without relying solely on algebraic methods.

Publications and Teaching

Authorial Works

Michael Sipser's most prominent authorial contribution is his textbook Introduction to the Theory of Computation, first published in 1996 by PWS Publishing Company. The book systematically explores the foundational areas of , including finite automata, context-free languages, computability via Turing machines, and classes such as and . Subsequent editions expanded its scope and refined its presentation: the second edition appeared in 2006 from Course Technology, and the third in 2012 from Cengage Learning, incorporating updated examples, additional exercises, and enhanced clarity for diverse learners. Widely regarded as the premier resource for computational theory courses, the text has become a staple in undergraduate and graduate curricula worldwide due to its rigorous yet accessible structure that builds concepts progressively from regular languages to undecidability and beyond. It emphasizes intuitive explanations over rote memorization, making abstract ideas approachable while maintaining mathematical precision. The book's strength lies in its detailed treatment of core concepts, such as the and of Turing machines to illustrate universal computation, and the proof techniques for reductions that highlight the practical implications of theoretical limits. These sections provide step-by-step derivations and visual aids, aiding readers in grasping the hierarchy of computational power without overwhelming technicality. In addition to the main text, Sipser has produced accompanying materials, including comprehensive problem sets integrated into each edition and separate solution manuals for instructors, which reinforce learning through a mix of exercises ranging from basic verifications to advanced proofs. These resources have supported its adoption in courses like MIT's 18.404J, where they facilitate hands-on engagement with the material.

Pedagogical Impact

Michael Sipser has taught MIT's course 18.404/6.840, Introduction to the Theory of Computation, for over four decades since joining the faculty in 1980, with the course remaining active as of fall 2025. The course covers core topics in computability and complexity, including finite automata, context-free languages, Turing machines, undecidability, and classes such as P, NP, and PSPACE, serving as a foundational offering for both mathematics and computer science undergraduates and graduates. Through weekly lectures and recitations, Sipser has guided thousands of students in developing proof-based reasoning skills essential to theoretical computer science. Central to Sipser's teaching approach in this course are problem sets and exams designed to foster intuitive understanding of abstract concepts rather than rote . The course features six problem sets, each focusing on key proofs and applications, such as constructing automata or analyzing decidability, with submissions emphasizing clear logical steps over exhaustive . Exams, including a midterm allowing a crib sheet, similarly prioritize conceptual grasp, encouraging students to connect theoretical models to broader implications in . This method aligns with Sipser's emphasis on the "big picture" in , helping students appreciate the subject's relevance without delving into unnecessary technical minutiae. His textbook serves as the primary companion for these materials, reinforcing intuitive insights through examples and exercises. Sipser has also mentored numerous graduate students, supervising 17 PhD theses primarily on topics in , such as interactive proofs and circuit lower bounds. Notable advisees include Andrew , whose 2007 dissertation on arithmetic circuits earned the George M. Sprowls Prize, and others like Lance Fortnow and , who advanced through their work under his guidance.

Awards and Honors

Professional Recognitions

Michael Sipser was elected a Fellow of the American Academy of Arts and Sciences in 2009, recognizing his foundational contributions to and . In 2016, he was named a Fellow of the for his advancements in and his leadership in the mathematical community. Sipser received the ACM Fellowship in 2017, awarded by the Association for Computing Machinery for contributions to , particularly randomized computation and . Additionally, in 2015, he was honored with the Distinguished Alumni Award for his distinguished career in following his PhD from the institution.

Educational Distinctions

Michael Sipser has been recognized multiple times for his exceptional contributions to teaching and student advising at . In 1984, 1989, and 1991, he received the MIT Graduate Student Council Teaching Award, which honors faculty members nominated by graduate students for outstanding instruction. These awards highlight his early impact in the classroom, particularly in courses on . In 2003, Sipser was awarded the MIT School of Science Student Advising Award, acknowledging his dedication to mentoring and guiding students in their academic and professional development. Sipser's commitment to earned him the Margaret MacVicar Faculty Fellowship in 2016, MIT's highest honor for excellence in undergraduate teaching, which provides support for continued pedagogical innovation. That same year, he shared the Irwin Sizer Award for the Most Significant Improvement to with colleague Tom Leighton, recognizing their collaborative development of the Course 18C major in Mathematics with , which integrates rigorous mathematical training with computational principles. These distinctions underscore Sipser's influence in shaping accessible and innovative curricula, including his renowned course.

Personal Life and Recent Activities

Family and Residence

Michael Sipser is married to Ina Sipser. They have two children: a daughter, , who graduated from , and a son, , who graduated from the . The family resides in , close to the MIT campus where Sipser has spent much of his professional career.

Current Engagements

As of 2025, Michael Sipser continues to serve as the Donner Professor of Mathematics at , where he is actively involved in teaching advanced courses in . In Fall 2025, he is instructing the graduate-level course "" (18.404J/6.540J), which covers foundational topics including automata, , and , with assessments including a midterm on and a final exam. On April 23, 2025, Sipser delivered the Kieval Lecture at , titled "Beyond Computation," presented in Malott Hall and followed by a reception; this event highlights his ongoing contributions to public discourse on theoretical limits in computing. Sipser has taken a prominent role in MIT's faculty governance, co-chairing the on and Campus Expression alongside Anette (Peko) Hosoi since its formation in fall 2023; the committee's work on fostering open dialogue and protecting expressive rights was featured in the MIT Faculty Newsletter for May/June 2025. His research interests remain centered on and , with recent scholarly attention to his foundational 1980s results on Bounded-Error Probabilistic Polynomial time (BPP). For instance, a January 2025 entry on the Computational Complexity blog referenced Sipser's proof that BPP lies in the , underscoring its enduring influence in discussions of randomness and derandomization.

References

  1. [1]
    Michael Sipser - WorldCat Entities
    Michael Sipser. Download. URI: https://id.oclc.org/worldcat/entity ... Significant Dates. 09/17/1954. Date of birth. Other Identifiers. n99004310. NUKAT ID.
  2. [2]
    Michael Sipser | American Academy of Arts and Sciences
    Professor of Applied Mathematics and Head of Mathematics Department. Founder of modern complexity theory as it is pursued today.Missing: biography | Show results with:biography
  3. [3]
    Michael Sipser - MIT Mathematics
    Michael Sipser is the Donner Professor of Mathematics and member of the Computer Science and Artificial Intelligence Laboratory at MIT. He received his PhD from ...
  4. [4]
    MIT Club of Beijing Annual Reception
    ### Biographical Summary of Michael Sipser
  5. [5]
    Michael Fredric Sipser - The Mathematics Genealogy Project
    Michael Fredric Sipser, MathSciNet, Ph.D. University of California, Berkeley 1980 UnitedStates, Dissertation: Nondeterminism and the Size of Two-Way Finite ...Missing: biography | Show results with:biography
  6. [6]
    Michael Sipser - Prabook
    Michael Sipser. mathematician, teacher, computer scientist. Michael Fredric ... Sipser was born and raised in Brooklyn, New York and moved to Oswego, New ...<|control11|><|separator|>
  7. [7]
    Michael Sipser named dean of the School of Science | MIT News
    Jun 5, 2014 · Michael Sipser, the Barton L. Weller Professor of Mathematics and ... A native of Brooklyn, N.Y., Sipser earned his BA in mathematics ...
  8. [8]
    https://news.mit.edu/2014/michael-sipser-named-dean-school-science
  9. [9]
    https://newspaperarchive.com/oswego-palladium-times-aug-22-1974-p-14
  10. [10]
    Sipser appointed Acting Dean of the School of Science | The Tech
    Sipser joined the MIT faculty in 1980, after completing a Bachelors of Arts in mathematics from Cornell University in 1974 and PhD in engineering from UC ...
  11. [11]
    Michael Sipser to step down as School of Science dean | MIT News
    Feb 19, 2020 · 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 ...Missing: early | Show results with:early
  12. [12]
    Michael Sipser - MIT Mathematics
    Bio. Michael Sipser is a theoretical computer scientist. He is the Donner Professor of Mathematics, a member of CSAIL, and served as the Dean of Science at MIT ...
  13. [13]
    Ph.D. Dissertations - 1980 - UC Berkeley EECS
    Michael F. Sipser [advisor: Manuel Blum]. Preferred Access in Packet ... Graduate Admissions & Programs · Courses · Prospective Women Students · Current ...
  14. [14]
    Michael Sipser | MIT CSAIL Theory of Computation
    Michael Sipser is a Professor and Chairman of Applied Mathematics. He received his Ph.D. from the University of California/Berkeley in1979 under the ...<|control11|><|separator|>
  15. [15]
    Lower bounds on the size of sweeping automata - ACM Digital Library
    Lower bounds on the size of sweeping automata. Author: Michael Sipser ... Published: 30 April 1979 Publication History. 26citation157Downloads. Metrics.
  16. [16]
    Four professors named 2016 MacVicar Faculty Fellows - MIT News
    Mar 7, 2016 · Sipser was promoted to associate professor in 1983 and full professor in 1989. Before his appointment as dean of science in 2014, Sipser ...
  17. [17]
    Michael Sipser - MIT CSAIL
    Dec 11, 2017 · Michael Sipser is a Professor and Chairman of Applied Mathematics. He received his Ph.D. from the University of California/Berkeley in1979.Missing: biography | Show results with:biography
  18. [18]
    Kaiser, Sipser to head departments - MIT News
    Mar 30, 2005 · In 1996 he was promoted to associate professor, and in 2002 he became a full professor. He holds a B.S. in biochemistry from Harvard ...
  19. [19]
    Tomasz Mrowka named interim head of the Department ... - MIT News
    Jun 16, 2014 · On June 5, Sipser was named dean of the School of Science, after serving since last December as interim dean, and since 2004 as head of the ...Missing: administrative | Show results with:administrative
  20. [20]
    Nergis Mavalvala named School of Science dean | MIT News
    Aug 17, 2020 · Astrophysicist Nergis Mavalvala has been named the new dean of MIT's School of Science, effective Sept. 1. She will succeed Michael Sipser.
  21. [21]
    Ad Hoc Committee on Academic Freedom and Campus Expression
    The Committee is co-chaired by Professors Michael Sipser and Anette (Peko) Hosoi. In order to ensure committee members have robust discussions around these ...
  22. [22]
    Ad Hoc Committee on Academic Freedom and Campus Expression ...
    The CAFCE will aim to establish a healthy foundation for academic freedom, civility, and the inclusion of a diversity of voices on campus.
  23. [23]
    [PDF] BPP and the Polynomial Hierarchy | Semantic Scholar
    A complexity theoretic approach to randomness · M. Sipser. Computer Science, Mathematics. STOC. 1983. We study a time bounded variant of Kolmogorov complexity ...
  24. [24]
    GO Is Polynomial-Space Hard | Journal of the ACM
    It is proved that GO is Pspace hard by reducing a Pspace-complete set, TQBF, to a game called generalized geography, then to a planar version of that game, and ...
  25. [25]
    [PDF] Expander Codes - Information Theory, IEEE Transactions on
    Expander Codes. Michael Sipser and Daniel A. Spielman. Abstract-Using expander graphs, we construct a new family of asymptotically good, linear error ...
  26. [26]
    [quant-ph/0001106] Quantum Computation by Adiabatic Evolution
    Jan 28, 2000 · Abstract: We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution.
  27. [27]
    [PDF] Quantum Computation by Adiabatic Evolution - cs.Princeton
    Abstract. We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state ...
  28. [28]
    A complexity theoretic approach to randomness - ACM Digital Library
    A complexity theoretic approach to randomness. Author: Michael Sipser. Michael ... Computational complexity and cryptography · Complexity classes · Models of ...
  29. [29]
    A complexity theoretic approach to randomness - Semantic Scholar
    We study a time bounded variant of Kolmogorov complexity. This notion, together with universal hashing, can be used to show that problems solvable ...
  30. [30]
    [PDF] A topological view of some problems in complexity theory
    A TOPOLOGICAL VIEW OF SOME PROBLEMS IN COMPLEXITY THEORY. Michael Sipser. Mathematics Department. Massachusetts Institute of Technology. Cambridge ...Missing: aspects | Show results with:aspects
  31. [31]
    A topological view of some problems in complexity theory
    ... In a series of papers from the early 1980s, Michael Sipser initiated the program in which one attacks the P = NP problem by investigating analogies in the ...Missing: aspects | Show results with:aspects
  32. [32]
    Study-Unit Description - Courses - L-Università ta' Malta
    Main Text/s and any supplementary readings: • Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, ISBN 053494728X, 1997
  33. [33]
    Introduction to the Theory of Computation | ACM SIGACT News
    Introduction to the Theory of Computation. Author: Michael Sipser. Michael ... Published: 01 March 1996 Publication History. 286citation13,036Downloads.
  34. [34]
    Introduction to the Theory of Computation, 3rd Edition - Cengage
    30-day returnsThe number one choice for today's computational theory course, this highly anticipated revision retains the unmatched clarity and thorough coverage.
  35. [35]
    Introduction to the Theory of Computation: Sipser, Michael
    ISBN-10. 0534950973 ; ISBN-13. 978-0534950972 ; Edition. 2nd ; Publisher. Course Technology ; Publication date. February 15, 2006.
  36. [36]
    18.404/6.5400 Introduction to the Theory of Computation
    It has an errata web site. You may use the 2nd edition but it is missing some additional practice problems, or the International Edition but it numbers some ...
  37. [37]
    Theory of Computation | Mathematics | MIT OpenCourseWare
    ... complex problems, oracles, probabilistic computation, and interactive proof systems ... Professor Michael Sipser teaching Lecture 14 of Theory of Computation.Missing: PhD | Show results with:PhD
  38. [38]
    [PDF] Introduction To The Theory Of Computation - Michael Sipser
    I have tried to make both the Exercises and Problems interesting chal- lenges. THE FIRST EDITION. Introduction to the Theory of Computation first appeared as a ...
  39. [39]
    https://math.mit.edu/directory/profile.html?pid=272
  40. [40]
    Andrew Sutherland - MIT Mathematics
    D. in mathematics in 2007 under the supervision of Michael Sipser. He was awarded the George M. Sprowls Prize for his thesis. After joining the MIT Department ...
  41. [41]
    [PDF] NEWS FROM THE MATHEMATICS DEPARTMENT AT MIT
    Mike. Sipser, now dean of the School of Science, truly modernized the department's leadership during his. 10 years as head, with Integral one of his many ...
  42. [42]
    2016 Class of the Fellows of the AMS - American Mathematical Society
    Michael Sipser, Massachusetts Institute of Technology. For contributions to complexity theory and for leadership and service to the mathematical community.<|control11|><|separator|>
  43. [43]
    Michael Sipser - ACM Awards
    ACM awards recognize achievements by young computing professionals, educators, theoretical computer scientists, software systems innovators, and pioneers ...
  44. [44]
    CS Distinguished Alumni Award Winners - EECS at Berkeley
    Michael Sipser (PhD 1980, advisor: Manuel Blum), Dean of Science, MIT. 2015 ... Cornell Tech and Professor of Public Health at Weill Cornell Medical College.
  45. [45]
    Awards - MIT Mathematics
    2016 ; Michael Sipser, Margaret MacVicar Faculty Fellow, MIT ; Michael Sipser, Irwin Sizer Award for the Most Significant Improvement to MIT Education, MIT.
  46. [46]
    Students compete in programming competitions during IAP - The Tech
    Feb 8, 2018 · “The class is difficult because the field we're teaching is hard … a lot of prerequisite knowledge is needed,” Aaron Sipser '19, president ...
  47. [47]
    [PDF] Theory of Computation Michael Sipser 18.404/6.5400 Fall 2025 ...
    One midterm (25% of grade) on October 16, 2025 during a class session and one final. (50% of grade) during finals week. Both exams are closed book. No access to ...Missing: current engagements<|control11|><|separator|>
  48. [48]
    Kieval Lecture Series | Department of Mathematics
    The Kieval Lecture will be held on April 23, 2025 in 228 Malott Hall at 4:30 p.m.. There will be a reception from 4:00 - 4:30 in 532 Malott Hall. “Beyond ...Missing: engagements | Show results with:engagements
  49. [49]
    Looking Back (FNL May/June 2025) | MIT Faculty Governance
    In fall of 2023, we formed and charged a Committee on Academic Freedom and Campus Expression. This group of faculty, staff, and students, led by Mike Sipser ...
  50. [50]
    Lautemann's Beautiful Proof - Computational Complexity
    Jan 29, 2025 · Once you have a hard function you can use their generator to derandomize BPP. But Lautemann's proof is incredibly beautiful because he just ...Missing: derandomization | Show results with:derandomization