Computer Science

Computational Complexity Theory0368.3168.01 
Fall 2013/14 

Complexity Theory: A Modern Approach, by Sanjeev Arora and Boaz Barak 

Introduction to the Theory of Computation, by Michael Sipser (1st or 2nd edition only) 

Computational Complexity, by Christos H. Papadimitriou 

Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone. 

Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan 

Approximation Algorithms, by Vijay V. Vazirani 

Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest 
Week 
Class Topic 
Recitaion Topic 
Recitaion Notes 
Homework 
1 
Introduction 
Introduction Complexity Functions Turing Machines P NP 

2 
Turing Machines Basic Complexity Classes Reductions 
Multitape TM Diagonalization CoNP 

3 
Reductions (cont) Space Complexity NL Savitch's Theorem 
Padding Argument NPC Reductions NLC Reductions 

4 
Immerman's Theorem Concentration of measure 
C vs. coC Space vs Time NL and coNL 

5 
Approximation Gap Problems 
MaxCut Hardness Gap Problems MaxCut Approximation MaxCut Derandomization 

6 
PCP Statement Gap Preserving Reductions Constraint Satisfaction Graphs 
2SAT Gap Preserving Reductions MAX2SAT Hardness of Approximation 

7 
Gap Amplification Polynomial Hierarchy 
Constraint Satisfaction Graphs Gap Amplification Independent Set Approximation Hardness 
No HW 

8 
Midterm BPP 
Midterm Solution Student Questions 
No HW 

9 
delta CSG Unique Games 
delta CSG 

10 
The Polynomial Hierarchy BPP 
The Polynomial Hierarchy BPP 

11 
IP Error Correcting Codes 
Error Correcting Codes 

12 
Error Correcting Codes (cont) 
Error Correcting Codes (cont) 

13 

14 