What is … (algebraic) complexity theory?

This page hosts information on Jesko Hüttenhain's talk "What is … (algebraic) complexity theory?" at the "What is …?" seminar. The talk will take place on Friday, February 6, 1:00pm at the BMS Loft at Urania. This talk will help you better understand the talk by Joseph M. Landsberg, which will start at 2pm.

Abstract

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.

Comments