Algebraic Geometry and Representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science

2021/08/13 by Landsberg, J. M. · 1 citation
#13F20 #14L30 #14L35 #15A69 #68Q15 #68Q17 #Algebraic Geometry (math.AG) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Representation Theory (math.RT)

paper · doi:10.48550/arxiv.2108.06263

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.

Cited by

• TokenBlowUp: Resolving Representational Singularities in LLM Token Spaces via Monoidal Transformations

Related

• Determination Problems for Orbit Closures and Matrix Groups
• Arithmetic invariant theory
• Geometry and the complexity of matrix multiplication
• Implementing geometric complexity theory: On the separation of orbit\n closures via symmetries
• The complexity of matrix multiplication: developments since 2014. Extended abstract of 2018 Oberwolfach Complexity meeting plenary lecture