Algebraic Complexity Seminar

Algebraic Complexity: Basic Motivation, Definitions, and Structural Results

I will motivate the study of algebraic models of computation from the viewpoint of boolean complexity theory, and show how this motivates a diverse set of questions (circuit lower bounds, polynomial identity testing, and circuit reconstruction). After discussing the relations between these questions, I'll define various models of computation (formulas, algebraic branching programs, circuits) and prove some basic structural results such as depth-reduction and homogenization.