About this course

\( \def\DTIME{\mathsf{TIME}} \def\NTIME{\mathsf{NTIME}} \def\DSPACE{\mathsf{DSPACE}} \def\NSPACE{\mathsf{NSPACE}} \def\P{\mathsf{P}} \def\NP{\mathsf{NP}} \def\L{\mathsf{L}} \def\NL{\mathsf{NL}} \def\PSPACE{\mathsf{PSPACE}} \def\NPSPACE{\mathsf{NPSPACE}} \def\EXP{\mathsf{EXP}} \def\NEXP{\mathsf{NEXP}} \def\RP{\mathsf{RP}} \def\coRP{\mathsf{coRP}} \def\ZPP{\mathsf{ZPP}} \def\PP{\mathsf{PP}} \def\FP{\mathsf{FP}} \def\sharpP{\#\mathsf{P}} \def\BPP{\mathsf{BPP}} \def\AC{\mathsf{AC}} \def\NC{\mathsf{NC}} \def\SC{\mathsf{SC}} \)

This is an introductory course on algebra and computation. In this offering of the course, we will look at algebraic models of computation with a focus on arithmetic circuits computing multivariate polynomials.

The main goal of the course this course is to understand the following interconnected questions.

• Arithmetic Circuit Lower bounds: Given an explicit family of polynomials that cannot be computed by small sized arithmetic circuits.

• Polynomial Identity Testing: Given a polynomial as a circuit, can we test efficiently if the polynomial is identically zero or not.

• Hitting sets: Designing hitting sets for algebraic models.

The course will introduces the necessary basic algebra required. No background in algebra is expected. In this course, we will be looking at a selected subset of the following topics. For a tentative plan (in action), please check the lecture summaries page.

• Algebraic complexity classes (VP, VNP, VSAC) and related structural results - Homogenization (Strassen), Interpolation, Depth reduction for formula (Brent, Spira). Depth reduction for circuits (Hyafil and Valiant-Skyum-Berkhowitz-Rackoff). Reduction to depth $4$ (Agarwal-Vinay).

• Combinatorial characterisation of permanent polynomial via cycle covers and determinant polynomial via clow sequences (Mahajan-Vinay). Ben-Or Cleve construction.

• Basic lower bounds - Baur-Strassen lowerbound and computing partial derivatives, Kalarkoti’s quadratic formula lower bounds. Determinantal complexity lower bounds, Migon’s lower bound.

• Lower bounds for restricted settings (“Natural approaches”) - Monotone circuit lower bound (Jerrum-Snir). Measure based lower bounds for restricted depth 3 circuits (Nisan-Wigderson) and quadratic lower bound for general depth $3$ (Shpilka-Wigderson). Lower bound for depth $3$ circuits due to Grigoriev and Karpinski.

• Restricted models and lower bounds against them: Read-once ABPs. Nisan’s characterisation.

• Separations - multilinear ABPs and formulas; multilinear circuits and formulas via Dyck polynomials; monotone circuits and monotone ABPs; monotone VP and monotone VNP.

• Lower bounds for multilinear models - Lower bound for multilinear formula (Raz and Raz-Yehudayoff). Lower bounds for constant depth circuits - Limaye-Srinivasan-Tavenas’s result

• Collapses - In the multlinear world, VP is same as VNP (Mahajan-Saurabh).

• Related settings: Non-commutative setting - non-commutative ABPs, Nisan’s characterisation of ABPs, Hadamard products, Finite automata based lower bounds. Border Complexity and introduction to geometric complexity theory.

• PIT and connections to algebraic circuit lower bounds. Hardness versus randomness trade-offs for small depth circuits. Introduction to Hitting Set Generators.

• Constructing PIT for depth 2 circuits and depth 3 powering circuits. Shpilka-Volkovich generator.

• Forbes-Shpilka quasi-polynomial time PIT for ROABPs.

• PIT for constant depth circuits

• Barriers to algebraic circuit lower bounds. Succinct hitting sets and algebraic natural proofs.

The course syllabus can be found here

Links to similar courses

• Ramprasad Saptarishi's course page
• Chandan Saha's course page
• Nitin Saxena's course page
• Mrinal’s course page