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

COALESCE Combinatorially and Algebraically Decomposing Search spaces: Better Worst-case Bounds for Hard Search Tasks

Coordinator
Universiteit Utrecht, Netherlands
Runs
1 May 2025 to 30 April 2030
Status
Running
EU funding
€1.9m
Total cost
€1.9m
Partners
1 organisations in 1 countries
Type
European Research Council grant
Grant agreement
101171685

What the project is doing

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

Search tasks are computational tasks with a curious property: while their solutions are easily verifiable when given, finding those solutions from scratch appears much more arduous. A central algorithmic paradigm to solve such tasks is that of search space decomposition. This paradigm solves a search task by breaking it up in subtasks such that a solution to the original problem can be quickly recovered from solutions of the subtasks.

Despite its basic nature and its ubiquitous use, it still holds many mysteries. The mission of COALESCE is to develop a broad theory to design and analyze search space decompositions to solve fundamental search tasks as fast as possible in the standard model of worst-case analysis. Strikingly, such a theory has not been developed yet. Our theory will be a coalescence of two established theories:- Combinatorial search space decompositions have been studied for graph problems in the area of width parameters, but only focus on decomposing the input and not the search space.- Algebraic decompositions such as factorizations of matrices and tensors that are of low rank or sparse, have been studied in the area of algebraic complexity, but only for very few problems and not in combination with search space decompositions.

In this proposal, I identify concrete research problems from Parameterized and Fine-Grained Complexity (two prominent subfields of Theoretical Computer Science) that serve as stepping stones towards a model for search space decompositions beyond input decompositions, as well as a theory to analyse their algorithmic power based on combinatorial and algebraic decompositions. Now is the right moment for this project: the joint power of combinatorial and algebraic decompositions is still barely understood and not yet fully exploited.

COALESCE will combine these (and many more) tools in novel ways that transcend existing approaches, and bring a rich theory on the search space decomposition methods entirely within reach.

Who is involved

OrganisationCityCountryRole
Universiteit UtrechtUtrechtNetherlandsCoordinator

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