Computer Science

Computational Complexity Theory0368.3168.01 
Winter 2012/13 














Week 
Class Topic 
Recitaion Topic 
Recitaion Notes 
HomeWork 
1 
Introduction Turing Machines 
Introduction Complexity Functions Turing Machines 

2 
Basic Complexity Classes 
P and NP Karp reductions 

3 
NPC CookLevin theorem 
NPC 

4 
Space complexity NL Savitch's Theorem 
The Padding Argument Definitions of NL 

5 
Immerman's Theorem 
Immerman's Theorem (proof again) Savitch and some examples 

6 
Approximation algorithms: vertex Cover, independent set, TSP Definition of gap problems 
Greedy algorithm for approximation of MinVC Gap problem of MaxCut 

7 
The PCP theorem: hardness of approximation 
Hardness of approximation of MAX2SAT 

8 
CSG and Amplification Clique approximation is hard to any factor 
CSG and Amplification 
No HomeWork 

9 
TQBF is PSPACEComplete Quiz 
SubsetSum is NPC GapSubsetSum[1e,1] is easy 
10 
BPP, PH BPP is in Sigma2 
BPP Amplification 
11 

Approximation factor 3/2 for TSP with triangle enequality Uniqueness in triplets 

12 
Hardness of approximation of coloring Random walks 
Reproof the reduction from kCSG to qGSG_Delta 


13 
Error Correcting Codes 
2SAT is in NL (NLC) UniqueGame 

14 
Error Corecting codes 
Error correcting codes Random codes 
No HW 