Fall 2014

Algebraic Complexity Seminar

Friday, Sep 12, 2014 11:00 am – 12:00 pm 

Add to Calendar


Michael Forbes (Massachusetts Institute of Technology)


Calvin Lab 116

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.