Arithmetic Circuits (Summer 2023)
General information
Instructor : Mrinal Kumar
Email : first name DOT last name AT tifr DOT res DOT in
Time : Wed, 9:30 am-12:30 pm
Location : A238 (Tentative)
Office hours : please send me an email
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.
- Problem set 2.
Lectures
- Lecture 01 (May 24) : Introduction to arithmetic circuits, VP, VNP, Permanent in VNP via Ryser's formula, Csanky's algorithm for Determinant
- Lecture 02 (May 31) : Algebraic branching programs, Homogenization, Interpolation, Division Elimination, Shallow circuits for Elementary symmetric polynomials
- Lecture 03 (Jun 07) : Balancing formulas, Hyafil's depth reduction, VSBR depth reduction, Reduction to depth 4
- Lecture 04 (Jun 14) : Reduction to depth 3, Polynomial factorization
- Lecture 05 (Jun 21) : Polynomial factorization contd: root computation via Newton Iteration
- Lecture 06 (Jun 28) : Polynomial factorization contd: computing arbitrary factors, Existence of hard polynomials, Lower bound of Strassen and Baur & Strassen
- Lecture 07 (Jul 05) : Lower bounds for Algebraic Branching Programs and Formulas
- Lecture 08 (Jul 12) : Lower bounds for multilinear computation
- Lecture 09 (Jul 19) : PIT for sparse polynomials, derandomization from algebraic hardness
- Lecture 10 (Jul 26) : Lower bounds for constant depth circuits. (Guest lecture by Ramprasad Saptharishi)
Topics that we planned to cover but didn't
- Lecture 11 : Whitebox PIT for Non-Commutative formulas, Blackbox PIT for diagonal circuits
- Lecture 12 : Ben-Or and Cleve, parallel algorithms for bipartite matching
- Lecture 13 : Complexity of linear transformations - Morgenstern's lower bound, Matrix Rigidity, Shoup-Smolensky's lower bound
- Lecture 14 : Tensor rank and arithmetic circuits - Strassen's connection, Raz's connection to formula lower bounds
References