- 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
| Organisation | City | Country | Role |
|---|---|---|---|
| Tel Aviv University | Tel Aviv | Israel | Coordinator |
Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI