Fall 2018

Geometric Complexity Theory: Complexity Lower Bounds Using Algebraic Geometry and Representation Theory II

Wednesday, August 22nd, 2018 11:00 am12:00 pm

Add to Calendar

Algebraic complexity theory studies the complexity of multivariate polynomials over a fixed field. The classical models of computation are algebraic circuits, algebraic formulas, algebraic branching programs, and determinants of affine linear forms. If the ground field is the real or complex numbers, then the set of polynomials of complexity at most n lies dense in an algebraic variety. Studying its geometric structure dates back to early work by Mulmuley and Sohoni (2001), and also Bürgisser (2001). Analogous studies have been conducted much earlier by Bini et al. (1979, 1980) in the setting of tensors when studying matrix multiplication. Following Mulmuley and Sohoni, we carefully adjust the algebraic complexity measures so that set of polynomials of complexity at most n becomes an algebraic variety that is endowed with a group action of the general linear group. This enables us to study complexity lower bounds using representation theory. No prior knowledge about algebraic complexity theory, algebraic geometry, or representation theory is needed for this talk.