Date 
Topics covered 
Notes 
Remarks 
Week 1 

Mon April 1 
Introduction 
Notes 

Wed April 3 
Turing machines 
Notes
1, Notes
2 

Fri April 5 
Nondeterministic Turing machines 
Notes
1, Notes
2 

Week 2 

Mon April 8 
More on nondeterminism, BigO complexity 
Notes
1, Notes
2 

Wed April 10 
Discussion about group projects and HW1 


Fri April 12 
Unrecognizable/undecidable languages 
Notes 
HW 1 due 
Week 3 

Mon April 15 
Graphs and more examples of
languages in NP 
Notes 

Wed April 17 
Discussion about rings, fields and HW2 


Fri April 19 
NPcompleteness and SAT 
Notes 

Week 4 

Mon April 22 
The CookLevin theorem 
Notes 

Wed April 24 
Discussion 


Fri April 26 
Complexity of polynomials 
Notes 
HW 2 due 
Week 5 

Mon April 29 
Complexity and expression size, pcomputability 
Notes 

Wed May 1 
The determinant and permanent polynomials 
Notes 

Fri May 3 
Review/discussion 


Week 6 

Mon May 6 
Midterm 

HW 3 due 
Wed May 8 
Group discussions 


Fri May 10 
Group discussions 


Week 7 

Mon May 13 
Group discussions 


Wed May 15 
pdefinability and the class VNP 
Notes 

Fri May 17 
perm_n is in VNP (Class in ART
317) 
Notes 
Project proposals due 
Week 8 

Mon May 20 
Determinantal expressions and VP_e
hardness of det_n 
Notes 

Wed May 22 
Group discussions 


Fri May 24 
VNPcompleteness of perm_n 
Notes 

Week 9 

Mon May 27 
No class! Memorial day 


Wed May 29 
discussion 


Fri May 31 
Valiant's conjecture and dc(perm_3) 

HW 4 due 
Week 10 

Mon Jun 3 
Discussion 



Wed Jun 5 
Discussion 


Fri Jun 7 
Discussion 


Final 

Wed June 12 
Final examination, 2:30  4:20 pm 

MGH 271 