Content (Tentative)

Introduction

• Aritmetic circuits, formulas, VP, VNP, division elimination
• Determinant in VP, Algebraic branching programs (ABP) and Determinant
• Bipartite matching in Randomized NC

Structural results

• Homogenization for circuits, formulas, Baur & Strassen
• Factors of polynomials with small arithmetic circuits
• Depth reduction for formulas
• Depth reduction for circuits
• Depth reduction to depth-4
• Depth reduction to depth-3
• Width-3 ABP (Ben-Or & Cleve) and Width-2 ABP (Allender & Wang)

Lower bounds

• Lower bound for general circuits (Strassen)
• Lower bound for formulas (Kalorkoti)
• Lower bound for constant depth circuits (Shoup & Smolensky, Raz)
• Lower bound for non-commutative ABPs (Nisan)
• Partial derivatives and lower bound for homogeneous depth-3 circuits (Nisan & Wigderson)

Derandomization

• PIT - blackbox vs whitebox, Klivans-Spielman generator
• PIT for Non-commutative ABPs (Raz & Shpilka)
• Lower bounds vs PIT (Kabanets & Impagliazzo)