ERC Starting Grant · 2022
Investigating the Conjectures of Fine-Grained Complexity
Fine-grained complexity theory identifies a small set of conjectures under which a large number of hardness results hold. The fast-growing list of such conditional hardness results already spans many diverse areas of computer science. Improved algorithms for some of the most central problems in these domains are deemed impossible unless one of the core conjectures turns out to be false, terminating decades-long quests for faster algorithms. Much research is going into closing the remaining gaps, addressing more domains, and achieving beyond-worst-case results. But should these conjectures, that are the foundation of this entire theory, really be treated as laws of nature? In addition to…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.