## Topic outline

• • ### General Information

The lectures will be given in English. HW will be given every two-three weeks. Final grades will be based on HW, participation in class, and final exam/project.

• ### Literature

Most of the material can be found in the following two surveys:

More material can be found in:

A comprehensive resource is the following book:

• Algebraic Complexity Theory, by Peter Bürgisser, Michael Clausen and Amin Shokrollahi. The book can be found at the library.

• ### Homework

• ### Lecture 1

Arithmetic circuit, arithmetic formula, VP, VNP, Reductions, Det, Perm, Valiant's hypothesis

• ### Lecture 2

ABP, formulas <= ABPs <= circuit, Det is complete for ABPs, Perm is complete for VNP (via ABPs)

• ### Lecture 3

Relation between Valiant's hypothesis and Cook's hypothesis (without proof).

Brent's theorem (balancing formulas)

Homogenization for circuits, formulas. Interpolation.

Hyafil's depth reduction for circuits (to quasi-poly size)

• ### Lecture 4

VP=VNC^2 [Valiant-Skyum-Berkowitz-Rackoff]

Reduction to Depth 4 [Raz, Agrawal-Vinay, Koiran, Tavenas]

Computing first order partial derivatives [Baur-Strassen]

• ### Lecture 5

Universal Circuit

Getting Rid of division gates

Simulating extension fields with small fields

Strassen's lower bound for general circuits

Algebraic rank and Kalorkoti's complexity measure

• ### Lecture 6

Completed Kalorkoti's formula lower bound

Lower bound for monotone circuits

Dimension of partial derivatives as complexity measure

Lower bounds for $\Sigma\bigwedge\Sigma$ circuits

Lower bounds for homogeneous $\Sigma\Pi\Sigma$ circuits

Lower bounds for $\Sigma\Pi\Sigma$ circuits

• ### Lecture 7

Partial derivative matrix

Lower bounds for read-once Oblivious ABPs (ROABPs)

Raz's Lower bound for multilinear formulas

• ### Lecture 8

Construction of a full rank polynomial that has a poly-size multilinear circuit

Raz-Yehudayoff lower bounds for constant depth multilinear circuits

Razborov-Smolensky lower bound for constant depth AC^0[p] circuits

• ### Lecture 9

Grigoriev-Karpinsky and Grigoriev-Razborov lower bound for depth 3 circuits over finite fields

Shifted Partial derivative measure

• ### Lecture 10

Completed lower bound for the NW_k polynomial by depth-4 circuits

Started discussing PIT, hitting sets, generators

Existence of hitting sets

BB PIT implies lower bounds

• ### Lecture 11

Lower bounds imply PIT for general arithmetic circuits

White Box PIT implies either NEXP does not have poly-sized circuits or Perm does not have poly-size circuits

BB PIT for ∑∏ circuits

• ### Lecture 12

Reconstruction of ∑∏ circuits

White Box PIT ROABPs (saw in detail for $\Sigma\bigwedge\Sigma$ circuits)

BB PIT for RO-Det

Sylvester-Gallai theorem

• ### Lecture 13

PIT of ∑∏∑ circuits using Sylvester-Gallai theorem (White box and black box)

Rank-preserving dimension reduction

Newton-Raphson iteration and finding roots of multivariate polynomials

Natural proofs, GCT and other vegetables