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 5 
Administrivia Introduction Regular Languages Contextfree Languages 
1 out 
Problem
Set 1
POW1 
[S] 1, 2 
Jan 12 
Turing Machines and Decidability The ChurchTuring Thesis Variants of Turing machines Decidable problems concerning regular and contextfree languages The Halting Problem 
POW2

[S] 3.13.3, 4.14.2 

Jan 19 
Reducibility Reductions Post's Correspondence Problem 
1 due; 2 out 
Problem
Set 2
POW3 
[S] 5.15.3 
Jan 26 
Time Complexity Lower bounds for singletape Turing machines P and NP 
POW4

[S] 7.17.3 [K] 1 

Feb 2 
NPCompleteness Polytime reductions CookLevin Theorem 
2 due; 3 out 
PS1
Solutions

[S] 7.47.5 
Feb 9 
NPCompleteness reductions Space Complexity Savitch's Theorem 
POW5
Problem Set 3 
[S] 8.1, 8.4 [K] 23 

Feb 16 
Space Complexity,
contd. ImmermanSzelepcsenyi Theorem Logspace Computability 
3 due; 4 out 
PS2
Solutions

[S] 8.48.5 [K] 46 
Feb 23 
Space Complexity,
contd. PSPACE and PSPACEcompleteness 

Problem
Set 4
POW6 
[S] 8.28.3, 10.2 [K] 8, 13, C 
Mar 2 
Spring Break 
PS3
Solutions 

Mar 9 
Alternation Alternating Turing Machines The PolynomialTime Hierarchy Hierarchy Theorems Separation results 
4 due Midterm out 
Midterm
PS4 Solutions 
[S] 9.19.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 79 
[S] 10.4 [K] 15 
Mar 30 
Interactive Proof
Systems IP = PSPACE 
POWs
1011

[S] 10.4 [K] 1617 

Apr 6 
Probabilistically
checkable proofs (PCP) Definition of the model Hardness of approximation Recursion Theorem and Applications 
5 due 
Problem
Set 6 POWs 1215 
[K] 18, 3334 [S] 10.6, 6.1 
Apr 12 
Decidability of Logical Theories 
Final out 
Final

[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