Hola,
¿eres nuevo aquí?

Registrate y conecta tu empresa con financiación pública, partners y proyectos.

CONJEXITY

Financiado

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 scie... ver más

30/11/2027

WEIZMANN

1M€

Presupuesto del proyecto: 1M€

Líder del proyecto

WEIZMANN INSTITUTE OF SCIENCE No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Ver 1 Participantes

Financiación concedida El organismo HORIZON EUROPE notifico la concesión del proyecto el día 2022-11-15

Línea de financiación objetivo El proyecto se financió a través de la siguiente ayuda:

ERC-2022-STG: ERC STARTING GRANTS

I+D

Cerrada hace 2 años

0% 100%

1 Participantes

WEIZMANN

1.50M€ | Lider

Proyectos interesantes

EPRICOT Efficient Proofs and Computation A Unified Algebraic Appro... 2M€ Cerrado

EXCICO Extremal Combinatorics and Circuit Complexity 180K€ Cerrado

CoCoSym Symmetry in Computational Complexity 1M€ Cerrado

ALGOCom Novel Algorithmic Techniques through the Lens of Combinatori... 1M€ Cerrado

PID2019-109137GB-C22 SISTEMAS DE PRUEBA MAS ALLA DE RESOLUCION: ANALISIS TEORICO 37K€ Cerrado

NoShortProof Nonexistence of Short Proofs 231K€ Cerrado

Últimas noticias

27-11-2024: Videojuegos y creaci... Se abre la línea de ayuda pública: Ayudas para la promoción del sector del videojuego, del pódcast y otras formas de creación digital

27-11-2024: DGIPYME En las últimas 48 horas el Organismo DGIPYME ha otorgado 1 concesiones

27-11-2024: FUNDACION-EOI En las últimas 48 horas el Organismo FUNDACION EOI ha otorgado 2 concesiones

Duración del proyecto: 60 meses Fecha Inicio: 2022-11-15
Fecha Fin: 2027-11-30

Líder del proyecto

WEIZMANN INSTITUTE OF SCIENCE

TRL 4-5

Presupuesto del proyecto 1M€

Descripción del proyecto 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.

Conecta tu I+D

Entra hoy

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores