Skip to content

everything.study

6.089

Great Ideas in Theoretical Computer Science

Undergraduate · Historical course

Spring 2008

Topics

Introduction
Logic
Circuits and finite automata
Turing machines
Reducibility and Gödel
Minds and machines
Complexity
Polynomial time
P and NP
NP-completeness
NP-completeness in practice
Space complexity and more
Randomness
Probabilistic complexity classes
In-class midterm
Derandomization / cryptography double feature
Private-key cryptography
Public-key cryptography
Cryptographic protocols
Interactive proofs / machine learning
Probably Approximately Correct (PAC) learning
Learning, Chomsky, RSA, quantum
Quantum computing
Quantum algorithms

Readings

While the course will not closely follow any textbook, we will sometimes use Complexity Theory: A Modern Approach by Sanjeev Arora and Boaz Barak. A draft of this new book is available for free on the Web, and a printed version will be distributed in class. In addition, the following is highly recommended, though not required: ↗
Listed reading
Sipser, Michael. Introduction to the Theory of Computation . 2nd ed. Boston, MA: Course Technology, 2005. ISBN: 9780534950972.
Listed reading

Sources

Course catalogue ↗Historical OpenCourseWare
MIT OCW calendar ↗
MIT OCW syllabus ↗
Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.