Algebraic Geometry and Representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
Academic Article
Overview
Research
Additional Document Info
View All
Overview
abstract
Many fundamental questions in theoretical computer science are naturally expressed as special cases of the following problem: Let $G$ be a complex reductive group, let $V$ be a $G$-module, and let $v,w$ be elements of $V$. Determine if $w$ is in the $G$-orbit closure of $v$. I explain the computer science problems, the questions in representation theory and algebraic geometry that they give rise to, and the new perspectives on old areas such as invariant theory that have arisen in light of these questions. I focus primarily on the complexity of matrix multiplication.