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

EXACT Exact Aspects of Complexity Theory

Coordinator
Tel Aviv University, Israel
Runs
1 January 2027 to 31 December 2031
Status
Running
EU funding
€1.5m
Total cost
€1.5m
Partners
1 organisations in 1 countries
Type
European Research Council grant
Grant agreement
101297414

What the project is doing

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

The classical definition of efficient algorithms as those running in poly-time is long recognized as insufficient. In the era of big data, for example, a linear-time algorithm can be deemed feasible in situations where a quadratic one is not. On the other end of the spectrum, even modest improvements to the base of the exponent in an exp-time algorithm can dramatically expand the range of problem instances for which a solution remains viable.

This research aims to refine complexity theory by developing precise characterizations of worst-case running times for fundamental problems, identifying input instances that require that worst-case complexity, and establishing bidirectional relationships between the exact hardness of poly-time problems and NP-complete ones. More specifically, our major objectives are (1) Refine upper bounds on the running times of algorithms for core NP-complete problems (such as SAT, Graph Coloring, Subset Sum) to better ground, sharpen, or test fine-grained complexity conjectures; (2) Characterize the structure of worst-case instances for central NP-complete problems, agnostically to the running time itself; (3) Establish a bidirectional equivalence between the exact hardness of certain poly-time problems and NP-complete ones, building on insights from fine-grained complexity that provide one-directional reductions.

Our prior work includes significant advances in the relevant areas. We achieved the first improvements in decades for the running times of key NP-complete problems such as k-SAT and Graph Coloring. Additionally, we provided foundational conditional lower bounds for important approximation and graph algorithmic problems through fine-grained complexity theory. The fusion of expertise from exact algorithms and fine-grained complexity positions us uniquely to tackle the ambitious goals above.

Achieving those may establish a theory of completely tying up exact running times of efficient problems to classical conjectures such as NP!=P.

Topics

Who is involved

OrganisationCityCountryRole
Tel Aviv UniversityTel AvivIsraelCoordinator

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