Hola,
¿eres nuevo aquí?

Regístrate gratis y conecta tu empresa con financiación pública, partners y proyectos.

Tengo cuenta

Regístrate

Ver video

AUTAR

Financiado

Cerrado

A Unified Theory of Algorithmic Relaxations

For a large family of computational problems collectively known as constrained optimization and satisfaction problems (CSPs), four decades of research in algorithms and computational complexity have led to a theory that tries to c... ver más

30/09/2020

UPC

2M€

Presupuesto del proyecto: 2M€

Líder del proyecto

Universidad Politécnica de Cataluña No se ha especificado una descripción o un objeto social para esta compañía.

Total investigadores 9

Fecha límite participación Sin fecha límite de participación.

Ver 2 Participantes

Financiación concedida El organismo H2020 notifico la concesión del proyecto el día 2020-09-30

ERC-CoG-2014: ERC Consolidator Grant

I+D

Cerrada hace 10 años

0% 100% 100%

Información adicional privada

No hay información privada compartida para este proyecto. Habla con el coordinador.

2 Participantes

UPC

1.73M€ | Lider

FILMQUITY

Conecta tu I+D

¿Tienes un proyecto y buscas un partner? Gracias a nuestro motor inteligente podemos recomendarte los mejores socios y ponerte en contacto con ellos. Te lo explicamos en este video

Proyectos interesantes

PCPABF Challenging Computational Infeasibility PCP and Boolean fun... 2M€ Cerrado

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

NEAT Non-linear Existential Arithmetic Theories 181K€ Cerrado

PTCC Phase transitions and computational complexity 1M€ Cerrado

InfCSP Descriptive Complexity of Infinite Domain Constraint Satisfa... 195K€ Cerrado

OptApprox Strong Convex Relaxations with Optimal Approximation Guarant... 1M€ Cerrado

Duración del proyecto: 64 meses Fecha Inicio: 2015-05-27
Fecha Fin: 2020-09-30

Líder del proyecto

Universidad Politécnica de Cataluña No se ha especificado una descripción o un objeto social para esta compañía.

Total investigadores 9

Presupuesto del proyecto 2M€

Fecha límite de participación Sin fecha límite de participación.

Descripción del proyecto For a large family of computational problems collectively known as constrained optimization and satisfaction problems (CSPs), four decades of research in algorithms and computational complexity have led to a theory that tries to classify them as algorithmically tractable vs. intractable, i.e. polynomial-time solvable vs. NP-hard. However, there remains an important gap in our knowledge in that many CSPs of interest resist classification by this theory. Some such problems of practical relevance include fundamental partition problems in graph theory, isomorphism problems in combinatorics, and strategy-design problems in mathematical game theory. To tackle this gap in our knowledge, the research of the last decade has been driven either by finding hard instances for algorithms that solve tighter and tighter relaxations of the original problem, or by formulating new hardness-hypotheses that are stronger but admittedly less robust than NP-hardness. The ultimate goal of this project is closing the gap between the partial progress that these approaches represent and the original classification project into tractable vs. intractable problems. Our thesis is that the field has reached a point where, in many cases of interest, the analysis of the current candidate algorithms that appear to solve all instances could suffice to classify the problem one way or the other, without the need for alternative hardness-hypotheses. The novelty in our approach is a program to develop our recent discovery that, in some cases of interest, two methods from different areas match in strength: indistinguishability pebble games from mathematical logic, and hierarchies of convex relaxations from mathematical programming. Thus, we aim at making significant advances in the status of important algorithmic problems by looking for a general theory that unifies and goes beyond the current understanding of its components.

Conecta tu I+D

Entra hoy

¿Olvidé mi contraseña?

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores