Hola,
¿eres nuevo aquí?

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

NoShortProof

Financiado

Nonexistence of Short Proofs

Efficient algorithms are vital for dealing with the ever growing amounts of data in our modern world. A particularly tricky task is posed by so-called combinatorial problems, where objects need to be combined together to form a so... ver más

31/03/2026

UCPH

231K€

Presupuesto del proyecto: 231K€

Líder del proyecto

KOBENHAVNS UNIVERSITET No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Ver 2 Participantes

Financiación concedida El organismo HORIZON EUROPE notifico la concesión del proyecto el día 2024-03-07

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

HORIZON-MSCA-2023-PF-01-01: MSCA Postdoctoral Fellowships 2023

I+D

Cerrada hace 1 año

0% 100%

2 Participantes

UCPH

230.77K€ | Lider

UPC

N.D. | Participante

Proyectos interesantes

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

PID2021-126605NB-I00 NUEVA METODOLOGIA HOLISTICA PARA LA CONFIGURACION, COMPARACI... 127K€ Cerrado

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

EXCICO Extremal Combinatorics and Circuit Complexity 180K€ Cerrado

TIN2015-65460-C2-1-P OPTIMIZACION COMBINATORIA II: METODOS Y ESTRATEGIAS 56K€ Cerrado

BES-2013-062658 APLICACIONES DE OPTIMIZACION COMBINATORIA: DISEÑO, IMPLEMENT... 84K€ 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: 24 meses Fecha Inicio: 2024-03-07
Fecha Fin: 2026-03-31

Líder del proyecto

KOBENHAVNS UNIVERSITET

TRL 4-5

Presupuesto del proyecto 231K€

Descripción del proyecto Efficient algorithms are vital for dealing with the ever growing amounts of data in our modern world. A particularly tricky task is posed by so-called combinatorial problems, where objects need to be combined together to form a solution satisfying some specified constraints. Increasing data size quickly causes an exponential growth in the search space for such problems, and despite decades of effort no algorithms have been designed that are guaranteed to tame this combinatorial explosion. In practice, however, it is often possible to find algorithmic shortcuts that work reasonably well, although there is very limited scientific understanding of when and why this is the case. This points to a fundamental challenge: We need a better understanding of the power and limitations of modern algorithm design. An important tool for algorithm analysis is to describe its method of reasoning in a formal proof system. When the algorithm terminates, the execution trace can be viewed as a proof of correctness of the result computed. If we can prove mathematically that no short proofs exist for certain types of statements, then this shows that the algorithm cannot possibly solve the corresponding problems efficiently. The goal of this project is to shed light on proof systems corresponding to some of the most powerful algorithmic paradigms in wide use and to delineate their potential. One concrete objective is to study combinatorial and algebraic methods for solving well-known graph problems such as Clique. Another goal is to compare semidefinite programming to traditional algorithms for solving non-Gaussian component analysis (NGCA), a fundamental problem in statistical learning. I will do so by strengthening existing techniques for analyzing these proof systems and combining them in novel ways. In particular, one important challenge will be to study the setting where the power of a proof system needs to be understood for a distribution of problems from which the input is drawn.

Conecta tu I+D

Entra hoy

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores