Hola,
¿eres nuevo aquí?

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

PARAPATH

Financiado

Parameterized Complexity Through the Lens of Path Problems

Nowadays, numerous problems are known to be NP-hard, and hence unlikely to admit worst-case efficient algorithms. Fortunately, the field of Parameterized Complexity (PC) shows that the nutshell of hardness often lies in particular... ver más

30/06/2027

BGU

1M€

Presupuesto del proyecto: 1M€

Líder del proyecto

BENGURION UNIVERSITY OF THE NEGEV 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-06-29

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

ERC-2021-STG: ERC STARTING GRANTS

I+D

Cerrada hace 3 años

0% 100%

1 Participantes

BGU

1.50M€ | Lider

Proyectos interesantes

EXCICO Extremal Combinatorics and Circuit Complexity 180K€ Cerrado

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

CoCoSym Symmetry in Computational Complexity 1M€ Cerrado

NoShortProof Nonexistence of Short Proofs 231K€ Cerrado

CRACKNP Finding Cracks in the Wall of NP completeness 1M€ Cerrado

EPRICOT Efficient Proofs and Computation A Unified Algebraic Appro... 2M€ 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-06-29
Fecha Fin: 2027-06-30

Líder del proyecto

BENGURION UNIVERSITY OF THE NEGEV

TRL 4-5

Presupuesto del proyecto 1M€

Descripción del proyecto Nowadays, numerous problems are known to be NP-hard, and hence unlikely to admit worst-case efficient algorithms. Fortunately, the field of Parameterized Complexity (PC) shows that the nutshell of hardness often lies in particular properties (called parameters) of the instances. Here, we answer the fundamental question: What makes an NP-hard problem hard? Specifically, how do different parameters of an NP-hard problem relate to its inherent difficulty? Based on this knowledge, we design efficient algorithms for wide-classes of instances of NP-hard problems. At the heart of PC lies the study of path (or cycle) problems. The inception of PC was inspired by the Graph Minors Theory, where the resolution of DISJOINT PATHS is a cornerstone. Moreover, the study of k-PATH has led to a large number of major breakthroughs in PC over the past three decades. Still, (i) fundamental questions concerning path problems have remained unanswered, and (ii) close to nothing is known about the relations between the different techniques to solve path problems. The overarching goal of this proposal is to build a unified, deep theory to analyze parameterized path problems. As known techniques to solve path problems rely, individually, on Graph Minors Theory, Extremal Combinatorics, Matroid Theory, Exterior Algebra, and more, I will draw new deep connections between these fields (towards unification). Based on the new theory, I believe that I will be able to answer decades-old questions in PC, which will revolutionize the power of this field. This includes the establishment of an Efficient Graph Minors Theory, an optimality program for color-coding-amenable problems, and a machinery to refute the existence of polynomial Turing kernels. Answers to these questions will substantially reshape the future of the design of parameterized algorithms, graph algorithms, and preprocessing procedures. Additionally, they will have high impact applications in practice.

Conecta tu I+D

Entra hoy

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores