Hola,
¿eres nuevo aquí?

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

EPRICOT

Financiado

Efficient Proofs and Computation A Unified Algebraic Approach

Computational complexity lies at the heart of information and computer science. Its aim is to formally understand the boundary between problems that can be solved efficiently and those that cannot. This has many applications: new... ver más

30/06/2026

IMPERIAL COLLEGE O...

2M€

Presupuesto del proyecto: 2M€

Líder del proyecto

IMPERIAL COLLEGE OF SCIENCE TECHNOLOGY AND ME... 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 H2020 notifico la concesión del proyecto el día 2021-04-13

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

ERC-2020-COG: ERC CONSOLIDATOR GRANTS

I+D

Cerrada hace 4 años

0% 100%

2 Participantes

IMPERIAL COLLEGE OF SCIENCE...

1.90M€ | Lider

CONSERVAS MARTIKO

Proyectos interesantes

EXCICO Extremal Combinatorics and Circuit Complexity 180K€ Cerrado

NoShortProof Nonexistence of Short Proofs 231K€ Cerrado

CONJEXITY Investigating the Conjectures of Fine-Grained Complexity 1M€ Cerrado

ExtenDD Coming to Terms: Proof Theory Extended to Definite Descripti... 2M€ Cerrado

CoCoSym Symmetry in Computational Complexity 1M€ Cerrado

PID2021-126605NB-I00 NUEVA METODOLOGIA HOLISTICA PARA LA CONFIGURACION, COMPARACI... 127K€ 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: 62 meses Fecha Inicio: 2021-04-13
Fecha Fin: 2026-06-30

Presupuesto del proyecto 2M€

Descripción del proyecto Computational complexity lies at the heart of information and computer science. Its aim is to formally understand the boundary between problems that can be solved efficiently and those that cannot. This has many applications: new algorithms are important to make progress in domains such as machine learning and optimization, and new complexity lower bounds (namely, computational impossibility results) are essential to provably secure cryptography. Beyond practical applications, these questions reveal deep mathematical and natural phenomena. One of the prominent directions to attack the fundamental lower bound questions in complexity comes from the study of resource bounded provability, namely proof complexity. Its aim is to understand which problems possess solutions with short correctness proofs and which do not. Traditionally, proof complexity is concerned with propositional (Boolean) logic, and thus techniques from Boolean function complexity have had a huge impact on the field, driving many of its results and agendas. In this proposal we suggest to employ recent breakthroughs in the field of proof complexity exploiting algebraic approaches to broaden in a systematic way both the scope and techniques of proof complexity, going from weak settings to the very strong ones, up to the major open problems in the field and beyond. In particular, we propose to use algebraic notions and techniques such as structural algebraic circuit complexity, rank lower bounds, noncommutative and PI algebras, among others to significantly broaden the arsenal of lower bound tools as well as develop new models and insights into proofs, computation and their inter-relations. This project has potential for a transformative impact in theoretical computer science and beyond, with applications to unconditional computational lower bounds, which underlie secure cryptography and derandomization of probabilistic algorithms, as well as improved SAT- and constraint-solving heuristics.

Conecta tu I+D

Entra hoy

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores