SPECTRA · Asymptotic spectra: from algebraic complexity theory to graph theory and beyond

What is the cost of a task if we have to perform it many times? This fundamental question appears throughout computer science (direct-sum problems), mathematics, and physics. Challenging, protagonistic problems of this kind, that play a central role in this proposal, are fast matrix multiplication in algebraic complexity theory, Shannon capacity in graph theory, efficient asymptotic entanglement transformations in quantum information, and the cap set problem in additive combinatorics. Despite tremendous effort, structured approaches avoiding known barriers have been lacking.Recent work by the PI has built the theory of asymptotic spectrum duality, which Strassen originally introduced to study matrix multiplication, into a powerful theory for direct-sum problems in various areas—from algebraic complexity, to discrete mathematics, quantum information and computational complexity—characterizing such problems in terms of an “asymptotic spectrum”. This approach opens a wealth of unexplored routes towards solving direct-sum problems via methods from algebra, analysis, combinatorics, and optimization.This proposal develops the asymptotic spectrum approach and synergetic applications to direct-sum problems: their general structure theory, methods for specific problems (matrix multiplication, Shannon capacity, and beyond), and interactions among them. Key objectives are: (1) to construct, through topological properties of asymptotic spectra, entirely new kinds of fast matrix multiplication algorithms and circumvent barriers of existing methods; (2) determine the Shannon capacity and its properties through a new approximation approach induced by asymptotic spectrum distance and structured (orbit) packings; (3) determine the structure (topological, geometric, computational) of asymptotic properties of quantum entanglement (tensors); and (4) develop the structural theory and broad applications of asymptotic spectra and interdisciplinary methods for direct-sum problems.