This is Jesko Hüttenhain's talk "What is ... (algebraic) complexity theory?" at the "What is ...?" seminar. The talk was given on Friday, February 06, 2014, 1:00pm at the BMS Loft at Urania.
Complexity theory is generally the study of algorithms, and the notion of an algorithm is mathematically not among the most accessible. In many cases however, we want to solve problems with an inherent mathematical structure, like multiplication of matrices. In algebraic complexity theory, we only look at very special classes of algorithms, those which have algebraic descriptions and interpretations. This way, stronger mathematical tools can be employed to answer computational questions. We give a short introduction to some of these algebraic models.
There was a mistake on one of the slides: Bilinear complexity is of course the same as tensor rank, and the Theorem by Strassen quoted at 21:14 refers to the circuit formulation (counting the number of nonscalar multiplications).
For more "What is ...?" seminar videos, visit whatisseminar.xyz.