logo
ProjectOngoing

Investigating the Conjectures of Fine-Grained Complexity

Location: Israel

Source: EU Funding & Tenders Portal

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, terminatin

Status
Under Construction
Location
Israel
Updated
22 Jul 2026
Source
EU Funding & Tenders Portal

ConstructChat

Ask ConstructChat about Investigating the Conjectures of Fine-Grained Complexity

Pick a question to edit it, or write your own.

First answer free · no account

I am a

Project Information FAQ

Project Information

3 Q
The project “Investigating the Conjectures of Fine-Grained Complexity” is an infrastructure initiative, located in Israel. Taiyo aggregates data on it from EU Funding & Tenders Portal.

Participants

Not available for this record.

Status

Original status

ongoing

Taiyo status

Under Construction

Taiyo last update

2026-07-22

Contact

Not available for this record.

Description

Description

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 three primary conjectures, the community has put forth about ten others. These ``secondary conjectures'' are often stronger variants of the primary conjectures, stating that the core problems remain hard despite introducing new assumptions on the input; they let us prove more hardness results but are also less extensively studied (and less likely to be true) compared to the original conjectures. Stepping away from current research that is hustling towards achieving tight bounds for all important problems under such conjectures, this project aims to investigate the conjectures themselves. Our main objective is to resolve the secondary conjectures; either by falsifying them or by establishing their equivalence to a primary conjecture. Either of these two outcomes would be satisfying: Refuting a conjecture must involve disruptive algorithmic techniques, impacting numerous other problems. Unifying a secondary conjecture with an original (primary) conjecture reinforces the validity of the conjecture and all its implications, solidifying the very foundations of Fine-Grained Complexity. We believe that there is a pressing need for such an investigation of this rapidly growing theory.

Location

Country

Israel

Source

Source

EU Funding & Tenders Portal

URL

More Details

Record type

Project

Article published date

2025-10-15

More on this project

Research

Free account

View all details

You are reading the public part. A free account opens the rest:

  • Every detail on this project
  • News and media coverage
  • Technical research
View all details

Free account · no card · lands you back on this project