Instructor : Mrinal Kumar

Email : last name AT cmsa DOT fas DOT harvard DOT edu

Prereq : CS 121/124/125 and Mathematical Maturity

Time : Friday, 10 am-1 pm

Location : MD G125 (Tentative)

Office hours : Thursday, 10am-11am

Multivariate polynomials have a ubiquitous influence in many areas of computer science, including, but not limited to, algorithm design, coding theory, combinatorics and pseudorandomness. Arithmetic circuits are a natural computational model which provide a succinct way to represent multivariate polynomials. They can be thought of as algebraic analogs of Boolean circuits, with elementary boolean operations (AND, OR, NOT) being replaced by elementary arithmetic operations (+, *, -, /) of polynomials.

The goal of this course is to provide a biased introduction to this area and to try and get a sense of the power and limitations of arithmetic circuits as a computational model. We hope to see a combination of both classical and recent results in this area, including some upper bounds, lower bounds and questions about factoring and derandomization. A tentative list of topics we will cover can be found here.

- Problem set 1 due on October 13.
- Problem set 2 due on November 17.

- Lecture 1 (Sep 1) : Introduction to arithmetic circuits, VP, VNP, Permanent in VNP via Ryser's formula, Csanky's algorithm for Determinant
- Lecture 2 (Sep 8) : Algebraic branching programs, Determinant via Clow Sequences, Homogenization, Interpolation, Shallow circuits for Elementary symmetric polynomials
- Lecture 3 (Sep 15) : Division elimination, Balancing formulas, Hyafil's depth reduction, VSBR
- Lecture 4 (Sep 22) : VSBR continued, Reduction to depth 4, Reduction to depth 3
- Lecture 5 (Sep 29) : Ben-Or and Cleve, Lovett's upper bound for all polynomials, Existence of hard polynomials
- Oct 6 : No class due to Additive Combinatorics Workshop at CMSA
- Lecture 6 (Oct 13) : Lower bound of Strassen and Baur & Strassen, Lower bounds for determinantal complexity, Lower bounds for homogeneous depth-3 circuit (Nisan-Wigderson)
- Lecture 7 (Oct 19, Make up class) : Parallel algorithms for bipartite matching, and PIT for sparse polynomials
- Lecture 8 (Oct 20) : Lower bounds for non-homogeneous depth-3 circuits over small fields, shifted partials and lower bounds for homogeneous depth-4 circuits with small bottom fan-in
- Lecture 10 (Oct 27) : Lower bounds for multilinear formulas, constant depth circuits
- Lecture 11 (Nov 3) : Whitebox PIT for Non-Commutative formulas, Blackbox PIT for diagonal circuits
- Lecture 12 (Nov 10) : PIT from lower bounds, complexity of roots of polynomials with small circuits
- Nov 17 : No class due to Algebraic Methods workshop at CMSA
- Lecture 13 (Dec 1) : student presentations

- Arithmetic Circuits : a survey of recent results and open questions

by Amir Shpilka and Amir Yehudayoff - A survey of known lower bounds in arithmetic circuits

by Ramprasad Saptharishi - Partial derivatives in arithmetic complexity and beyond

by Xi Chen, Neeraj Kayal and Avi Wigderson - Arithmetic circuit complexity

a course by Nitin Saxena at IITK - Arithmetic circuit complexity

a course by Neeraj Kayal and Chandan Saha at IISc Bangalore