| Date | Topics covered | Notes | Remarks | Week 1 |
|---|---|---|---|---|
| Mon April 1 | Introduction | Notes | ||
| Wed April 3 | Turing machines | Notes 1, Notes 2 | ||
| Fri April 5 | Non-deterministic Turing machines | Notes 1, Notes 2 | Week 2 | |
| Mon April 8 | More on non-determinism, Big-O 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 | NP-completeness and SAT | Notes | Week 4 | |
| Mon April 22 | The Cook-Levin 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, p-computability | 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 | p-definability 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 | VNP-completeness 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 |