Princeton University
Computer Science Dept.

Computer Science 487/Math 487
Theory of Computation

Sanjeev Arora

Fall 2010

General Information | Assignments | Handouts | Interesting Links|

Course Summary

Formal models of computation: finite automata and Turing machines. Universality of the model and the Church-Turning Thesis. Computability Theory ("What can or cannot be computed?") and Complexity Theory ("How efficient can a certain computation be?"). The P vs NP question and its status. NP-completeness and PSPACE- completeness. An introduction to complexity issues in application areas such as robotics, graphics, compilers, and cryptography. Introduction to some more advanced issues, such as "Why are we stuck on the P vs NP question?" "What is the power of randomness?" "What are zero knowledge proofs?" "Can quantum computers be much more powerful than current computers?" Prerequisites: COS 340/341 or equivalent math background (basically, ability to do math proofs).

About this course

This course teaches you to think rigorously about computation. It is considered part of the core training of a computer scientist. It is also pretty much self-contained, so it is an ideal course for CS nonmajors who wish to learn some computer science. In the past, the course has drawn students from math/science/engineering/philosophy. The course material is very elegant and inspiring and students usually like it. Here is some haiku about the course composed by students from a past year. (Note: the course has evolved since then, and covers some more topics.)

The textbook is Sipser's Theory of Computation; the later lectures will use  portions of Computational Complexity: A Modern Approach by Arora and Barak. Sipser's book is required, and Arora-Barak is optional.

Grading: 50% of the grade will be based upon assignments, which will be handed out every two weeks. Only 80\% of the assignment problems count towards your grade (i.e., at the end of the semester you get a full score if you correctly answer four out of every five problems assigned in homeworks).

There will be two takehome exams (in October and January). The take home exam in January can be downloaded from this page on the first day of reading period.

The exams are open-book.

There might also be a small project to do at the end of the semester.

Administrative Information

Lectures: Mon-Wed 1:30-2:50, Room: 105. Precepts: Tue 8:30-9:30, Room: 105

Professor: Sanjeev Arora - 307 CS Building - 258-3869 Office hrs: MW 3-4pm,  or by appointment.

Undergraduate Coordinator: Donna O'Leary - 410 CS Building - 258-1746

Teaching Assistant: Chris Beck


READINGS (from 2008 offering)

From the Sipser text we covered Chapters 1-4 completely. Then Sections 5.1, 5.3, and 6.2 (but not Theorem 6.17 which uses Section 6.1). Then we covered Chapters 7, 8 in full. (Chapter 4 of Arora-Barak also describes the basic results on space complexity.)

For the lecture on hierarchy theorems and limits of diagonalization read Arora-Barak Sections 3.1, 3.2, 3.5. (The other sections may be interesting to read for advanced students.)

For Polynomial Hierarchy, Arora-Barak Sections 5.1, 5.2.

For Circuits and Karp-Lipton Theorem, Arora-Barak Sections 6.1, 6.2.

For cryptography, Arora-Barak Sections 9.1, 9.2. The interactive proof concept is discussed in Chapter 8 but the example in class is all you are expected to understand.

For quantum computing, Arora-Barak Sections 10.1, 10.2 (but not 10.2.1), the Hadamard operation (p 183) and Section 10.5 (Simon's algorithm)


Honor Code for this class

Collaborating with your classmates on assignments is OK and even encouraged. You must, however, list your collaborators for each problem. The assignment questions have been carefully selected for their pedagogical value and may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.