Theory of Computation - 33403 - CS 7805

Instructor:  Emanuele Viola
Meetings: Monday and Wednesday, 2:50 pm - 4:30 pm, International Village 022.
Office Hours: After class in classroom and then in 246 West Village H.


This course provides a graduate-level introduction to the theory of computation. It is based on the following textbook:

[S] Introduction to the Theory of Computation, by Sipser, PWS Publishing Company, second edition, 2006. Some information about the book.

If you are interested in learning more about complexity theory, see the book by Arora and Barak, available online.

Scroll down to: class schedule, and homework policy.

Tentative syllabus

Regular languages. [S] 1.
Context-free languages. [S] 2.
Turing machines and decidability. [S] 3,4.
Reducibility. More undecidable problems. [S] 4.
Decidability of logical theories. [S] 6.2.
Kolmogorov complexity. [S] 6.4.
P, NP, and NP-completeness. [S] 7.
Space complexity. [S] 8.
Hierarchy theorems, relativization, circuits. [S] 9.
BPP. [S] 10.2.
The polynomial-time hierarchy. [S] 10.3.
Interactive proof systems, IP = PSPACE. [S] 10.4.
NC. [S] 10.5.

Class schedule

Jan 11. Administrivia. Overview of the course. Regular languages.
Reading: [S] 1.

Jan 13. Regular languages.
Reading: [S] 1. Problem set 1 out: Exercises 1.16, and 1.21, Problems 1.31, 1.32, 1.53, 1.56, 1.57.

Jan 18. Martin Luther King, no classes

Jan 20. Context-free languages.
Reading: [S] 2.

Jan 22. Makeup day: we meet in 108 WVG. Problem set 1 due.
Reading: [S] 2. Problem set 2 out: Exercise 2.14, 2.16, 2.17. Problems: 2.21, 2.37, 2.43, 2.44, 2.45.

Jan 25. Turing Machines. Reading: [S] 3

Jan 27. Decidability. The Halting problem. Reading: [S] 4

Feb 1. Undecidability. Reading: [S] 5. Problem set 2 due.
Problem set 3 out: Problems 3.9,3.14, 3.18, 4.17,5.9,5.18.

Feb 3. The recursion theorem. Reading: [S] 6

Feb 8. Decidability of logical theories. Reading: [S] 6

Feb 10. Inclement weather: No classes.

Feb 15. President's day. No classes.

Feb 17. Kolmogorov complexity. Reading: [S] 6.

Feb 19. Makeup day: we meet in 108 WVG. Problem set 3 due. Time complexity. Reading: [S] 7.
Problem set 4 out: 6.6, 6.7, 6.13, 6.15, 6.20, 6.22. In addition, solve either 6.16* or 6.25*.

Feb 22. Time complexity. Reading: [S] 7.

Feb 24. The Cook-Levin Theorem. Reading: [S] 7.

Spring break.

Mar 8. Space complexity. Reading: [S] 8.

Mar 10. Space complexity. Reading: [S] 8. Problem set 4 due.
Problem set 5 out: Problems 7.16, 7.23, 7.27, 7.36*, 7.44, 8.8, 8.16.

Mar 15. Space complexity: N, NL. Reading: [S] 8.

Mar 17. Intractability. Reading: [S] 9.

Mar 22. Emanuele away, no class.

Mar 24. Emanuele away, no class.

Mar 29. Relativization, circuit complexity. Reading: [S] 9.

Mar 31. BPP. Reading: [S] 10. Problem set 5 due.
Problem set 6 out: Problems 8.20, 8.27, 9.12, 9.13, 9.14, 9.20, 9.24, 9.25. For extra credit, solve 9.26* instead of 9.25.

Apr 5. Alternation. Reading: [S] 10

Apr 7. Interactive proofs. Reading: [S] 10

Apr 12. IP = PSPACE. Reading: [S] 10

Apr 14. NC, cryptography.
Problem 6 due.
Final problem set 7 out: Problems 10.9*, 10.13, 10.21

Apr 19. Patriot's day, no classes.

Apr 21. Advanced topic lecture: undirected connectivity in L

Apr 26. Advanced topic lecture: undirected connectivity in L
Problem 7 due.

Homework policy

Problems sets are due at the beginning of class. Late submissions are never accepted. Please submit your solutions on paper (not file). To hand them in: give it to me or slide them under my door West Village H (246).

Unless specified otherwise, in your solutions you can use the following and only the following: what proved in class, what proved in Sipser's book, and any basic fact you were supposed to know before taking this class. Anything else you must prove.

Strive to give effective, compact solutions. Your solutions should touch on all the main points, but long calculations or discussions are not required nor sought. Unless specified otherwise, you can collaborate, but you must acknowledge all your collaborators in your solutions.