CS G714: Theory of Computation

Spring 2009

Mailing list

Please join the class mailing list by following the instructions on the following webpage


Tentative Calendar

The reading assignments list section numbers from the second edition of Sipser's text ([S]) and lecture numbers from Kozen's text ([K]).  The numbers within the parenthesis are the corresponding sections and chapters in the first edition.

 Week  Topic Problem Sets
Jan 5
Regular Languages
Context-free Languages
1 out Problem Set 1
[S] 1, 2
Jan 12
Turing Machines and Decidability
The Church-Turing Thesis
Variants of Turing machines
Decidable problems concerning regular and context-free languages
The Halting Problem

[S] 3.1-3.3, 4.1-4.2
Jan 19
Post's Correspondence Problem
1 due; 2 out Problem Set 2
[S] 5.1-5.3
Jan 26
Time Complexity
Lower bounds for single-tape Turing machines
P and NP

[S] 7.1-7.3
[K] 1
Feb 2
Poly-time reductions
Cook-Levin Theorem
2 due; 3 out
PS1 Solutions
[S] 7.4-7.5
Feb 9
NP-Completeness reductions
Space Complexity

Savitch's Theorem

Problem Set 3
[S] 8.1, 8.4
[K] 2-3
Feb 16
Space Complexity, contd.
Immerman-Szelepcsenyi Theorem
Logspace Computability
3 due; 4 out
PS2 Solutions

[S] 8.4-8.5
[K] 4-6
Feb 23
Space Complexity, contd.
PSPACE and PSPACE-completeness

Problem Set 4
[S] 8.2-8.3, 10.2
[K] 8, 13, C
Mar 2
Spring Break

PS3 Solutions

Mar 9
Alternating Turing Machines
The Polynomial-Time Hierarchy
Hierarchy Theorems
Separation results
4 due
Midterm out
PS4 Solutions
[S] 9.1-9.2, 10.3
[K] 7, 9
Mar 16
Probabilistic Complexity
The class BPP
Midterm due

[S] 10.2
[K] 8, 13
Mar 23
Probabilistic Complexity
Undirected Connectivity is in RL
Interactive Proof Systems
Graph nonisomorphism
5 out
Problem Set 5
POWs 7-9

[S] 10.4
[K] 15
Mar 30
Interactive Proof Systems
POWs 10-11

[S] 10.4
[K] 16-17
Apr 6
Probabilistically checkable proofs (PCP)
Definition of the model
Hardness of approximation
Recursion Theorem and Applications
5 due
Problem Set 6
POWs 12-15

[K] 18, 33-34
[S] 10.6, 6.1
Apr 12
Decidability of Logical Theories
Final out

[S] 6.2
Apr 19
Finals week
Final due
PS5 Solutions
PS6 Solutions


Note: All handouts are in PDF.

References, especially for Interactive Proofs and the PCP Theorem

Complexity Theory: A Modern Approach
Sanjeev Arora and Boaz Barak, to be published by Cambridge University Press.

The PCP Theorem and Hardness of Approximation
A course at University of Washington, V. Guruswami and R. O'Donnell, Autumn 2005

The PCP theorem by gap amplification
I. Dinur, JACM 2007

On Dinur's Proof of the PCP Theorem
J. Radhakrishnan and M. Sudan

Complexity Theory
Notes from course taught at University of Maryland, College Park, Jonathan Katz, Fall 2005