Mailing list
Please join the class mailing list by
following the instructions on the following webpage
https://lists.ccs.neu.edu/bin/listinfo/csg714
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 
Handouts 
Reading 
Jan 7 
Administrivia Introduction The ChurchTuring Thesis; Variants of Turing machines 
1 out  Problem
Set 1 POW 1 
[S] 1, 2, 3.13.3 
Jan 14 
Decidability Decidable problems concerning regular and contextfree languages The Halting Problem 
POW 2 
[S] 4.14.2 

Jan 21 
Reducibility Reductions Post's Correspondence Problem 
1 due; 2 out  Problem
Set 2 POW 3 
[S] 5.15.3 
Jan 28 
Time Complexity Lower bounds for singletape Turing machines P and NP 
POW 4 
[S] 7.17.3 [K] 1 

Feb 4 
NPCompleteness Polytime reductions CookLevin Theorem 
2 due; 3 out 
Sample Solutions to PS1 
[S] 7.47.5 
Feb 11 
NPCompleteness reductions Space Complexity Savitch's Theorem 
POW 5 
[S] 8.1, 8.4 [K] 23 

Feb 18 
Space Complexity,
contd. ImmermanSzelepcsenyi Theorem Logspace Computability 
3 due; 4 out 
Sample Solutions to PS2 POW 6 
[S] 8.48.5 [K] 46 
Feb 25 
Space Complexity,
contd. PSPACE and PSPACEcompleteness 
Problem
Set 4 POW 7 & 8 
[S] 8.28.3, 10.2 [K] 8, 13, C 

Mar 3 
Spring Break 
Sample Solutions to PS3 

Mar 10 
Alternation Alternating Turing Machines The PolynomialTime Hierarchy Hierarchy Theorems Separation results 
4 due Midterm out 
Midterm 
[S] 9.19.2, 10.3 [K] 7, 9 
Mar 17 
Probabilistic Complexity The class BPP 
Midterm due 
Sample Solutions to PS4 
[S] 10.2 [K] 8, 13 
Mar 24 
Interactive Proof Systems Graph nonisomorphism IP = PSPACE 
5 out 
Problem
Set 5 POW 9 
[S] 10.4 [K] 1517 
Mar 31 
Probabilistically
checkable proofs (PCP) Definition of the model Hardness of approximation 
5 due;6 out  Midterm
sample solutions 
[K] 1819 
Apr 7 
More
on PCP NP is subset of PCP(poly(n),1) Oneway functions and basic crypto 
Problem
Set 6 POW 10 & 11 
[K] 1920 [S] 10.6 

Apr 14 
Recursion Theorem and Applications Decidability of Logical Theories 
6 due 
POW 12 
[S] 6.16.2 [K] 21, 3334 
Apr 21 
Finals week 
Sample
Solutions to PS5 Sample Solutions to PS6 Final Sample Solutions to Final 
Note: All handouts are in PDF.
Interactive Proofs and the PCP Theorem
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