QLunch: On the interplay between algebraic geometry and complexity theory

Speaker: Fulvio Gesmundo from QMATH

Title: On the interplay between algebraic geometry and complexity theory

Abstract:
Many problems in complexity theory can be formulated in terms of membership problems for suitable, classically studied, algebraic varieties, at least after some relaxation. We describe the general idea on which this approach is based and we illustrate some concrete examples: the complexity of matrix multiplication and its relation with secant varieties in spaces of tensors, the complexity of the DFT transform and its relation with matrix rigidity and, if time permits, Valiant's permanent vs determinant conjecture and its relation with the geometry of quasi-homogeneous spaces.