CS229r : Arithmetic Circuits (Fall 2017)
General information
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
Course description
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 sets
- Problem set 1 due on October 13.
- Problem set 2 due on November 17.
Summary of Lectures
- 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
References