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

Atlas / Israel

European Research Council grant · Running

CODY The Complexity of Dynamic Matrix Problems

Coordinator
The Hebrew University of Jerusalem, Israel
Runs
1 July 2022 to 30 June 2027
Status
Running
EU funding
€1.4m
Total cost
€1.4m
Partners
1 organisations in 1 countries
Type
European Research Council grant
Grant agreement
101039914

What the project is doing

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

Modern data analysis and optimization rely on our ability to process rapidly evolving dynamic datasets, often involving matrix operations in very high dimensions. Dynamic data structures enable fast information-retrieval on these huge databases by maintain- ing implicit information on the underlying data. As such, understanding the power and limitations of dynamic (matrix) data structures is a fundamental question in theory and practice.

Despite decades of research, there are still very basic dynamic problems whose complexity is (exponen- tially) far from understood – Bridging this gap is one of the centerpieces of this proposal. The second theme of this proposal is advancing the nascent role of dynamic data structures in continuous optimization. For over a century, the traditional focus of optimization research was on minimizing the rate of convergence of local-search methods.

The last ∼3 years have witnessed the dramatic potential of dynamic data structures in reducing the cost-per-iteration of (Newton type) optimization algorithms, proclaiming that the bottleneck to accelerating literally thousands of algorithms, is efficient maintenance of dynamic matrix functions. This new framework is only at its early stages, but already led to breakthroughs on decade-old problems in computer science.

This proposal will substantially develop this interdisciplinary theory, and identifies the mathematical machinery which would lead to ultra-fast first and second-order convex optimization. In the non-convex setting, this proposal demonstrates the game-changing potential of dynamic data structures and algebraic sketching techniques in achieving scalable training and inference of deep neural networks, a major challenge of modern AI.

Our program is based on a novel connection of Kernel methods and compressed sensing techniques for approximate matrix multiplication.

Topics

Who is involved

OrganisationCityCountryRole
The Hebrew University of JerusalemJerusalemIsraelCoordinator

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