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

Atlas / Belgium

Marie Skłodowska-Curie Action · Ended early

NeurExCo Synergizing Neural Network Theory and Combinatorial Optimization via Extension Complexity

Coordinator
Universite Libre De Bruxelles, Belgium
Runs
1 April 2024 to 31 March 2026
Status
Ended early
EU funding
€176k
Total cost
—
Partners
1 organisations in 1 countries
Type
Marie Skłodowska-Curie Action
Grant agreement
101153187

What the project is doing

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

Artificial intelligence is changing our lives. Artificial neural networks are present and entering various fields of modern technology such as medicine, engineering, education and many more. Even a small-scale theoretical understanding of why and how neural networks succeed in practice can have a considerable impact on the future development of such technologies. In contrast, combinatorial optimization is a well-established discipline at the intersection of mathematics and computer science, dealing with classical algorithmic questions like the Shortest Path or Traveling Salesperson Problems.

A powerful tool to study structural and algorithmic properties of combinatorial optimization problems is polyhedral geometry. For example, the geometric notion of extension complexity classifies how well a specific problem can be expressed and solved via an extremely successful general-purpose technique called linear programming. Recent developments show that polyhedral theory can also be a powerful tool to achieve a better mathematical understanding of neural networks.

The overall goal of this project is to significantly intensify the connection between neural networks and polyhedral theory, using the concept of extension complexity. This new symbiosis will advance both, the theoretical understanding of neural networks as well as the fundamental understanding of classical combinatorial optimization problems. On the side of neural networks, we expect to obtain new bounds on the required size and depth to solve a given problem, serving as an explanation of why large and deep neural networks are more successful in practice.

Furthermore, we expect contributions to a more refined understanding of the computational complexity to train a neural network. On the side of combinatorial optimization, we expect that generalized notions of extension complexity inspired by neural networks lead to new structural and algorithmic insights to classical problems like the matching problem.

Topics

Who is involved

OrganisationCityCountryRole
Universite Libre De BruxellesBruxellesBelgiumCoordinator

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