Algebraic Complexity Theory (2017II)
(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 nonzero polynomial?
 Reconstruction: Given oracle access to a polynomial computed by a circuit, can you construct a smallenough 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.
Problem sets
 Problem Set 1: [PDF] [TeX] (Deadline: September 3rd 2017)
 Problem Set 2: [PDF] [TeX] (Deadline: October 15th 2017)
 Problem Set 3: [PDF] [TeX] (Deadline: November 12th 2017)
Brief summary of lectures
 Lecture 1 (16082017)
 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 (18082017)
 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).

 [github]: Section 3.3.1, 3.3.2.

 [ACC IITK]: Lecture 3
 Lecture 3 (22082017)
 Homogenisation of circuits, interpolation, computing homogeneous components without blowing up depth, revisiting the elementary symmetric polynomial, another circuit for determinant via Gaussian elimination.

 [github]: Section 5.1, 5.2

 [SY10]: Section 2.5
 Lecture 4 (29082017)
 The MahajanVinay ABP for determinant, BenOr and Cleve

 [github]: Section 3.3.3

 [ACC IITK]: Lecture 12
 Lecture 5 (01092017)
 Depth reduction for formulas ([Brent, Spira]) and circuits ([Hyafil] and [ValiantSkyumBerkowitzRackoff])

 [github]: Section 5.3
 Lecture 6 (05092017)
 [ValiantSkyumBerkowitzRackoff] depth reduction continued, reduction to depth4 [AgrawalVinay, Koiran, Tavenas]

 [github]: Section 5.3
 Lecture 7 (08092017)
 Lower bound of [BaurStrassen], monotone circuit lower bound of [JerrumSnir].

 [github]: Section 6.1, Section 7.2
 Lecture 8 (12092017)
 Introduction to measure based lower bounds, lower bound of [NisanWigderson] for restricted depth3 circuits, quadratic lower bound of [ShpilkaWigderson] for general depth3 circuits (following a proof of [BalajiLimayeSrinivasan])

 [github]: Chapter 8
 Lecture 9 (15092017)
 Details of the proof of [BalajiLimayeSrinivasan], lower bound of [GrigorievKarpinski]

 [github]: Parts of chapter 8 and chapter 9
 Lecture 10 (22092017)
 Finishing the proof of [GrigorievKarpinski], towards lower bounds for multilinear models

 [github]: Parts of chapter 9 and chapter 11
 Lecture 11 (26092017)
 [Raz]’s lower bound for multilinear formulas

 [github]: Parts of chapter 11
 Lecture 12 (29092017)
 Finishing [Raz]’s lower bound for multilinear formulas, and [RazYehudayoff]’s lower bound for constant depth multilinear formulas

 [github]: Parts of chapter 11
 Lecture 13 (03102017)
 [Nisan]’s characterisation for noncommutative ABPs, hadamard products and [ArvindSrinivasan]’s hardness for the noncommutative determinant
 Lecture 14 (06102017)
 Shifted partial derivatives, and lower bounds for restricted depth4 circuits

 [github]: Parts of chapter 13
 Lecture 15 (09102017)
 Concluding the calculation of shifted partial derivatives for the NW polynomial, depth reduction to depth3 circuits.

 [github]: Parts of chapter 13 and 17
 Lecture 16 (13102017)
 Introduction to PIT and connections between PIT and lower bounds for algebraic circuits [KabanetsImpagliazzo, Agrawal, HeintzSchnorr]

 [SY10]: Chapter 4.3
 Lecture 17 (17102017)
 Hardnessrandomness tradeoffs in small depth ([DvirShpilkaYehudayoff]), introduction to hitting set generators
 Lecture 18 (20102017)
 Constructing PITs for depth2 circuits, and depth3 powering circuits

 [SY10]: Chapter 4.4
 Lecture 19 (24102017)
 Whitebox PIT for noncommutative ABPs and ROABPs [RazShpilka], introduction to basis isolation
 Lecture 20 (27102017)
 Basis isolating weight assignments, quasipolynomial time blackbox PIT for ROABPs [AgrawalGurjarKorwarSaxena], better hitting sets for depth3 powering circuits [ForbesSaptharishiShpilka]
 Lecture 21 (31102017)
 Algebraic independence, the Jacobian, and hitting sets from faithful maps [BeeckenMitmannSaxena, AgrawalSahaSaptharishiSaxena]

 “Unified approaches to PIT and lower bounds”: Chapter 4
 Lecture 22 (03112017)
 Hitting sets for Σ^{[k]}ΠΣ circuits ([KayalSaxena, SaxenaSeshadri])
 Lecture 23 (07112017)
 Border complexity and a brief introduction to Geometric Complexity Theory
 Lecture 24 (10112017)
 (tentative) Succinct hitting sets and candidate barriers to algebraic circuit lower bounds [ForbesShpilkaVolk]
 Lecture 25 (14112017)
 A brief glimpse into circuit reconstruction (sparse polynomials, roABPs and random multilinear formulas [GuptaKayalLokam])
 Lecture 26 (17112017)
 Things we didn’t covered in this course (Determinantal complexity [MignonRessayre], Elusive Functions [Raz], Projected shifted partials [KayalLimayeSahaSrinivasan, KumarSaraf])
 Lecture 27 (21112017)
 (Student presentation)
 Speaker: Prerona Chatterjee
 Title: Noncommutative circuits and sumofsquares problem [HrubesWigdersonYehudayoff]
 Lecture 28 (24112017)
 (Student presentation)
 Speaker: Anamay Tengse
 Title: Separating multilinear branching programs and formulas [DvirMalodPerifelYehudayoff]
References
 [SY10]: “Arithmetic Circuits: a survey of recent results and open questions” (Shpilka and Yehudayoff)
 [github]: A survey of known lower bounds in arithmetic circuits
 [ACC IITK]: Arithmetic circuit complexity course at IITK (by Nitin Saxena)
 [wact2016]: Workshop on Algebraic Complexity Theory (WACT) 2016