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 Context-free Languages |
1 out |
Problem
Set 1
POW-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 |
POW-2
|
[S] 3.1-3.3, 4.1-4.2 |
|
| Jan 19 |
Reducibility Reductions Post's Correspondence Problem |
1 due; 2 out |
Problem
Set 2
POW-3 |
[S] 5.1-5.3 |
| Jan 26 |
Time Complexity Lower bounds for single-tape Turing machines P and NP |
POW-4
|
[S] 7.1-7.3 [K] 1 |
|
| Feb 2 |
NP-Completeness 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 |
POW-5
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
POW-6 |
[S] 8.2-8.3, 10.2 [K] 8, 13, C |
| Mar 2 |
Spring Break |
PS3
Solutions |
||
| Mar 9 |
Alternation Alternating Turing Machines The Polynomial-Time Hierarchy Hierarchy Theorems Separation results |
4 due Midterm out |
Midterm
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 IP = PSPACE |
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 |
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