Investigating the Conjectures of Fine-Grained Complexity
This project aims to investigate secondary conjectures in fine-grained complexity theory, seeking to either falsify them or establish their equivalence to primary conjectures, impacting algorithmic foundations.
Projectdetails
Introduction
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.
Secondary Conjectures
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.
Project Objectives
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.
Expected Outcomes
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.
Financiële details & Tijdlijn
Financiële details
Subsidiebedrag | € 1.499.250 |
Totale projectbegroting | € 1.499.250 |
Tijdlijn
Startdatum | 1-12-2022 |
Einddatum | 30-11-2027 |
Subsidiejaar | 2022 |
Partners & Locaties
Projectpartners
- WEIZMANN INSTITUTE OF SCIENCEpenvoerder
Land(en)
Vergelijkbare projecten binnen European Research Council
Project | Regeling | Bedrag | Jaar | Actie |
---|---|---|---|---|
Algebraic Formula Lower Bounds and ApplicationsThis project aims to establish lower bounds for algebraic formulas and improve Polynomial Identity Testing algorithms by leveraging structural and algebraic techniques in theoretical computer science. | ERC Consolid... | € 1.869.055 | 2024 | Details |
The Hardness of Finding Good AlgorithmsThe project investigates the difficulty of finding efficient algorithms for various computational problems, aiming to establish lower bounds and connections to cryptography and learning theory. | ERC Starting... | € 1.498.664 | 2023 | Details |
New Frontiers in Information-Theoretic Secure ComputationThis project aims to enhance the understanding and efficiency of information-theoretic secure computation through improved secret sharing, secure reductions, and optimized protocols, impacting cryptography and theoretical computer science. | ERC Advanced... | € 2.113.125 | 2023 | Details |
Definable Algebraic TopologyThis project aims to enhance algebraic topology and coarse geometry by integrating Polish covers with homological invariants, leading to new classification methods and insights in mathematical logic. | ERC Starting... | € 989.395 | 2023 | Details |
Local-to-global Expansion and PCPsThis project aims to advance the study of Probabilistically Checkable Proofs using high-dimensional expansion theory to develop simpler PCP constructions and enhance local-to-global encoding understanding. | ERC Advanced... | € 2.105.840 | 2025 | Details |
Algebraic Formula Lower Bounds and Applications
This project aims to establish lower bounds for algebraic formulas and improve Polynomial Identity Testing algorithms by leveraging structural and algebraic techniques in theoretical computer science.
The Hardness of Finding Good Algorithms
The project investigates the difficulty of finding efficient algorithms for various computational problems, aiming to establish lower bounds and connections to cryptography and learning theory.
New Frontiers in Information-Theoretic Secure Computation
This project aims to enhance the understanding and efficiency of information-theoretic secure computation through improved secret sharing, secure reductions, and optimized protocols, impacting cryptography and theoretical computer science.
Definable Algebraic Topology
This project aims to enhance algebraic topology and coarse geometry by integrating Polish covers with homological invariants, leading to new classification methods and insights in mathematical logic.
Local-to-global Expansion and PCPs
This project aims to advance the study of Probabilistically Checkable Proofs using high-dimensional expansion theory to develop simpler PCP constructions and enhance local-to-global encoding understanding.