Seminal
The magazine and atlas of EU-funded researchA new publication from the web and AI team at Scott Charnley

Atlas / Netherlands

European Research Council grant · Running

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

Coordinator
Universiteit Van Amsterdam, Netherlands
Runs
1 January 2026 to 31 December 2030
Status
Running
EU funding
€1.5m
Total cost
€1.5m
Partners
1 organisations in 1 countries
Type
European Research Council grant
Grant agreement
101220349

What the project is doing

In the project's own words, from its summary on CORDIS.

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.

Topics

Who is involved

OrganisationCityCountryRole
Universiteit Van AmsterdamAmsterdamNetherlandsCoordinator

Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI