Notes for CSE 5329: Algebraic Complexity Theory, Autumn 2023

1. Algebraic Circuits

2. Elimination of Division Gates

3. Baur–Strassen Theorem

4. Finding the Shortest Cycle

5. Depth Reduction for Algebraic Formulas

6. Depth Reduction for Algebraic Circuits

7. Algebraic Branching Programs

8. Determinant is in VBP

9. Permanent is VNP-Complete, Part 1

10. Permanent is VNP-Complete, Part 2

11. Width-3 ABP, Nisan's Characterization

12. Strassen's Lower Bound, Bézout's Inequality

13. Bilinear Complexity, Tensor Rank, Matrix Multiplication Exponent

14. Non-Explicit Lower Bound, PIT, Hitting-Sets

15. PIT for Sparse Polynomials

16. Seeded Lossless Rank Extractors

17. PIT for Depth-3 Circuits via the Sylvester–Gallai Theorem

18. PIT for Depth-3 Circuits Over Any Field

19. Whitebox PIT for ROABPs

20. Blackbox PIT for ROABPs

Go back