נושאים
- מבוא
- General Information
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
Literature
Most of the material can be found in the following two surveys:
- A survey of lower bounds in arithmetic circuit complexity, by Ramprasad Saptharishi
- Arithmetic circuits: A survey of recent results and open questions, by Amir Shpilka and Amir Yehudayoff
More material can be found in:- Progress on Polynomial Identity Testing, by Nitin Saxena
- Progress on Polynomial Identity Testing-II, by Nitin Saxena
- Partial Derivatives in Arithmetic Complexity and beyond, by Xi Chen, Neeraj Kayal and Avi Wigderson
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
Lecture 1
Arithmetic circuit, arithmetic formula, VP, VNP, Reductions, Det, Perm, Valiant's hypothesis
- Lecture 2
Lecture 2
ABP, formulas <= ABPs <= circuit, Det is complete for ABPs, Perm is complete for VNP (via ABPs)
- Lecture 3
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
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
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
This paper gives a proof that there are hard polynomials with 0/1 coefficients. It also explains how to simulate extension fields using the base field.
- Lecture 6
Lecture 6
Completed Kalorkoti's formula lower bound
Lower bound for monotone circuits
Dimension of partial derivatives as complexity measure
Lower bounds for
circuits
Lower bounds for homogeneous
circuits
Lower bounds for
- Lecture 7
Lecture 7
Partial derivative matrix
Lower bounds for read-once Oblivious ABPs (ROABPs)
Raz's Lower bound for multilinear formulas
- Lecture 8
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
This is Smolensky's paper showing lower bounds for AC^0[p]
- Lecture 9
Lecture 9
Grigoriev-Karpinsky and Grigoriev-Razborov lower bound for depth 3 circuits over finite fields
Shifted Partial derivative measure
- Lecture 10
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
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
Lecture 12
Reconstruction of ∑∏ circuits
White Box PIT ROABPs (saw in detail for
circuits)
BB PIT for RO-Det
Sylvester-Gallai theorem
- Lecture 13
Lecture 13
PIT of ∑[3]∏∑ 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