Math 480: Algebraic Complexity Theory

Spring 2019

Lectures: MWF 11:30-12:20 in MGH 271
Instructor: Jarod Alper (
Office: PDL C-544
Office hours: Mon, Wed 3-4 pm

Textbook: Introduction to the Theory of Computation, 3rd edition, Michael Sipser

Addition resources will be posted here.

Syllabus: This course will consist of two parts. We will first discuss classical complexity theory following Sipser including the following topics: languages, decidability, deterministic and non-deterministic Turing machines, P vs NP, NP completeness and the Cook-Levin theorem. The second half of the course will introduce the algebraic analogues in terms of computability of polynomials. We will discuss: arithmetic circuits, arithmetic complexity, VP vs VNP, the determinant vs the perminant, Valiant's theorem on VNP-completeness of the permanent, determinantal complexity, Grenet's permanental formula, and the Mignon-Ressayre quadratic lower bound. Additional topics will be covered depending on time.

Resources This course is a very advanced undergraduate course and as such will likely be challenging. It may require different learning and studying strategies than lower level classes. Here are some links containing useful tips:
Homework: There will be regular homework assignments. The lowest homework score will be dropped. Homeworks are due in the beginning of class.

Schedule: The content of the lectures will be posted here.

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
Wed June 12 Final examination, 2:30 - 4:20 pm MGH 271

Midterm: There will be one in class midterm
Group poster project: In groups of 4, you will choose and study a specialized topic within complexity theory.

Group project details

Potential group projects

Useful resources:

Final poster presentation: