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 Church-Turing Thesis; Variants of Turing machines |
1 out | Problem
Set 1 POW 1 |
[S] 1, 2, 3.1-3.3 |
| Jan 14 |
Decidability Decidable problems concerning regular and context-free languages The Halting Problem |
POW 2 |
[S] 4.1-4.2 |
|
| Jan 21 |
Reducibility Reductions Post's Correspondence Problem |
1 due; 2 out | Problem
Set 2 POW 3 |
[S] 5.1-5.3 |
| Jan 28 |
Time Complexity Lower bounds for single-tape Turing machines P and NP |
POW 4 |
[S] 7.1-7.3 [K] 1 |
|
| Feb 4 |
NP-Completeness Poly-time reductions Cook-Levin Theorem |
2 due; 3 out |
Sample Solutions to PS1 |
[S] 7.4-7.5 |
| Feb 11 |
NP-Completeness reductions Space Complexity Savitch's Theorem |
POW 5 |
[S] 8.1, 8.4 [K] 2-3 |
|
| Feb 18 |
Space Complexity,
contd. Immerman-Szelepcsenyi Theorem Logspace Computability |
3 due; 4 out |
Sample Solutions to PS2 POW 6 |
[S] 8.4-8.5 [K] 4-6 |
| Feb 25 |
Space Complexity,
contd. PSPACE and PSPACE-completeness |
Problem
Set 4 POW 7 & 8 |
[S] 8.2-8.3, 10.2 [K] 8, 13, C |
|
| Mar 3 |
Spring Break |
Sample Solutions to PS3 |
||
| Mar 10 |
Alternation Alternating Turing Machines The Polynomial-Time Hierarchy Hierarchy Theorems Separation results |
4 due Midterm out |
Midterm |
[S] 9.1-9.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] 15-17 |
| Mar 31 |
Probabilistically
checkable proofs (PCP) Definition of the model Hardness of approximation |
5 due;6 out | Midterm
sample solutions |
[K] 18-19 |
| Apr 7 |
More
on PCP NP is subset of PCP(poly(n),1) One-way functions and basic crypto |
Problem
Set 6 POW 10 & 11 |
[K] 19-20 [S] 10.6 |
|
| Apr 14 |
Recursion Theorem and Applications Decidability of Logical Theories |
6 due |
POW 12 |
[S] 6.1-6.2 [K] 21, 33-34 |
| 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