Algebraic Circuit Complexity (2017-II)

(Tue 1400 — 1530) & (Fri 1400 — 1530) @ A 201

The course would deal with understanding the complexity of multivariate polynomials, where the measure of complexity is the size of the smallest algebraic circuit computing it (similar to a boolean circuit, but now basic operations are additions and multiplications of polynomials). We will deal with three kinds of questions in this field (and the three questions are intimately connected to each other):

  • Lower bounds: Can you show that an explicit polynomial requires large circuits to compute it?
  • Polynomial Identity testing: Given a circuit as input, can you test efficiently if the circuit is computing a non-zero polynomial?
  • Reconstruction: Given oracle access to a polynomial computed by a circuit, can you construct a small-enough circuit from this?

Grading

The course will have 3 problem sets (contributing 60% overall to the final evaluation). The remaining 40% of the evaluation would be based on a chapter contributed to the [github] survey on some lower bound exposition.

Brief summary of lectures

Lecture 1 (16-08-2017)
Introduction to algebraic complexity, VP, VNP, notion of reduction and completeness, proof that Perm is in VNP via Ryser’s formula.
  • [github]: Parts of chapter 1 and 2 (introduction and preliminaries)
Lecture 2 (18-08-2017)
Reducing formulas to projections of determinants, elementary symmetric polynomials and small circuits for them (via dynamic programming, and Newton identities), proof that Det is in VP (via Newton Identities).
Lecture 3 (22-08-2017)
Homogenisation of circuits, interpolation, computing homogeneous components without blowing up depth, revisiting the elementary symmetric polynomial, another circuit for determinant via Gaussian elimination.
Lecture 4 (29-08-2017)
The Mahajan-Vinay ABP for determinant, Ben-Or and Cleve
Lecture 5 (01-09-2017)
Depth reduction for formulas ([Brent, Spira]) and circuits ([Hyafil] and [Valiant-Skyum-Berkowitz-Rackoff])
Lecture 6 (05-09-2017)
[Valiant-Skyum-Berkowitz-Rackoff] depth reduction continued, reduction to depth-4 [Agrawal-Vinay, Koiran, Tavenas]
Lecture 7 (08-09-2017)
Lower bound of [Baur-Strassen], monotone circuit lower bound of [Jerrum-Snir].
Lecture 8 (12-09-2017)
Introduction to measure based lower bounds, lower bound of [Nisan-Wigderson] for restricted depth-3 circuits, quadratic lower bound of [Shpilka-Wigderson] for general depth-3 circuits (following a proof of [Balaji-Limaye-Srinivasan])
Lecture 9 (15-09-2017)
Details of the proof of [Balaji-Limaye-Srinivasan], lower bound of [Grigoriev-Karpinski]
  • [github]: Parts of chapter 8 and chapter 9
Lecture 10 (22-09-2017)
Finishing the proof of [Grigoriev-Karpinski], towards lower bounds for multilinear models
  • [github]: Parts of chapter 9 and chapter 11
Lecture 11 (26-09-2017)
[Raz]’s lower bound for multilinear formulas
Lecture 12 (29-09-2017)
Finishing [Raz]’s lower bound for multilinear formulas, and [Raz-Yehudayoff]’s lower bound for constant depth multilinear formulas
Lecture 13 (03-10-2017)
[Nisan]’s characterisation for non-commutative ABPs, hadamard products and [Arvind-Srinivasan]’s hardness for the non-commutative determinant
Lecture 14 (06-10-2017)
Shifted partial derivatives, and lower bounds for restricted depth-4 circuits
Lecture 15 (09-10-2017)
Concluding the calculation of shifted partial derivatives for the NW polynomial, depth reduction to depth-3 circuits.
Lecture 16 (13-10-2017)
Introduction to PIT and connections between PIT and lower bounds for algebraic circuits [Kabanets-Impagliazzo, Agrawal, Heintz-Schnorr]
Lecture 17 (17-10-2017)
Hardness-randomness tradeoffs in small depth ([Dvir-Shpilka-Yehudayoff]), introduction to hitting set generators
Lecture 18 (20-10-2017)
Constructing PITs for depth-2 circuits, and depth-3 powering circuits
Lecture 19 (24-10-2017)
Whitebox PIT for non-commutative ABPs and ROABPs [Raz-Shpilka], introduction to basis isolation
Lecture 20 (27-10-2017)
Basis isolating weight assignments, quasipolynomial time blackbox PIT for ROABPs [Agrawal-Gurjar-Korwar-Saxena], better hitting sets for depth-3 powering circuits [Forbes-Saptharishi-Shpilka]
Lecture 21 (31-10-2017)
Algebraic independence, the Jacobian, and hitting sets from faithful maps [Beecken-Mitmann-Saxena, Agrawal-Saha-Saptharishi-Saxena]
Lecture 22 (03-11-2017)
Hitting sets for Σ[k]ΠΣ circuits ([Kayal-Saxena, Saxena-Seshadri])
Lecture 23 (07-11-2017)
Border complexity and a brief introduction to Geometric Complexity Theory
Lecture 24 (10-11-2017)
(tentative) Succinct hitting sets and candidate barriers to algebraic circuit lower bounds [Forbes-Shpilka-Volk]
Lecture 25 (14-11-2017)
A brief glimpse into circuit reconstruction (sparse polynomials, roABPs and random multilinear formulas [Gupta-Kayal-Lokam])
Lecture 26 (17-11-2017)
Things we didn’t covered in this course (Determinantal complexity [Mignon-Ressayre], Elusive Functions [Raz], Projected shifted partials [Kayal-Limaye-Saha-Srinivasan, Kumar-Saraf])
Lecture 27 (21-11-2017)
(Student presentation)
Speaker: Prerona Chatterjee
Title: Non-commutative circuits and sum-of-squares problem [Hrubes-Wigderson-Yehudayoff]
Lecture 28 (24-11-2017)
(Student presentation)
Speaker: Anamay Tengse
Title: Separating multilinear branching programs and formulas [Dvir-Malod-Perifel-Yehudayoff]

References