Computational Complexity and Algebra - Spring 2009

• Mar 9: Introduction, straight line programs, algebraic computation trees, etc. division free programs for polynomials a la Strassen.
• Mar 16: Unbounded degree decision trees. Verifying the Max requires n-1 comparisons.
• Mar 23: Randomized unbounded degree trees - O((log n)^2) for finding the Max. Linear lower bound for verifying the median.
• Mar 30: Lower Bounds for Linear Decision Trees. Algebraic Computation Trees.
• Passover Break.
• Apr 20: Poly-Formula = ANC1, Product of n 3x3 matrices is p-complete for ANC1.
• Apr 27-May 4: Valiant's Complexity classes, VP, VNP, VQP, VNQP. VNP-Circuit = VNP-Formula.
• May 11: Det is p-complete in VP_{weakly-skew-circuits}; Baur-Strassen Thm on partial derivatives.
• May 18: Det Complexity of the Permanent is greater than c*n^2. Proof of bounds on the number of connected componnents of algebraic semi-varaties.
• May 25, June 1 & 8: The Geometric Complexity Theory approach of Ketan Mulmuley.
• June 15 & 22: Derandomizing Polynomial Identity Testing and Circuit Lower bounds.

• Characterizing Valiant's Algebraic Complexity Classes by Guillaume Malod and Natacha Portier.
• A quadratic lower bound for the permanent and determinant problem over any characteristic not equal 2 by Jin-Yi Cai, Xi Chen and Dong Li.
• Lower Bounds for Algebraic Computation Trees.
• Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds by Valentine Kabanets and Russell Impagliazzo.
• On P vs. NP, Geometric Complexity Theory, and The Flip I: a high-level view by Ketan Mulmuley.