ERC Starting Grant · 2025
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…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.