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

Atlas / Norway

European Research Council grant · Running

NewPC New Horizons of Parameterized Complexity

Coordinator
Universitetet I Bergen, Norway
Runs
1 January 2026 to 31 December 2030
Status
Running
EU funding
€2.5m
Total cost
—
Partners
1 organisations in 1 countries
Type
European Research Council grant
Grant agreement
101199930

What the project is doing

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

Parameterized Complexity (PC) provides an approach to moving beyond classic worst-case analysis of algorithms by focusing on multivariate algorithms whose performance is influenced by several parameters beyond input size. While it has been successful in various algorithmic domains, particularly those involving discrete objects like graphs, sets, matroids, or Boolean formulas, PC remains underutilized in areas involving geometric and algebraic objects such as points, vectors, linear spaces, or matrices.

This project seeks to revolutionize the PC field by developing novel multivariate algorithms for continuous optimization problems involving such objects. The performance of these algorithms—whether measured by approximation ratio, probability error, or running time—is highly sensitive to multiple parameters. The main challenge in advancing parameterized complexity to these new domains is the need for suitable algorithmic and complexity tools.

To address this challenge, the NewPC project proposes to revisit and revise fundamental methods for handling geometric and algebraic objects—such as dimension reduction, sampling, sketching, clustering, and coresets—through the conceptual questions of PC, including determining proper parameterization, quantifying the distance from triviality, and identifying when kernelization is possible. In short, the proposed Research Program can be summarized as:Questions of PC + Geometric Methods = New HorizonsThe proposed research will open new horizons in parameterized complexity by- Advancing multivariate approximation and lossy kernelization, both emerging areas within parameterized complexity.- Establishing multivariate algorithmic analysis as the standard tool for designing provably correct and efficient algorithms in domains such as computational geometry, machine learning, robust statistics, and optimization—areas where the classical worst-case algorithmic analysis often falls short.

Topics

Who is involved

OrganisationCityCountryRole
Universitetet I BergenBergenNorwayCoordinator

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