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

ALUNIF

Financiado

Cerrado

Algorithms and Lower Bounds A Unified Approach

One of the fundamental goals of theoretical computer science is to understand the possibilities and limits of efficient computation. This quest has two dimensions. The theory of algorithms focuses on finding efficient solutions to... ver más

28/02/2019

UOXF

1M€

Presupuesto del proyecto: 1M€

Líder del proyecto

THE CHANCELLOR MASTERS AND SCHOLARS OF THE UN... No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

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

Ver 2 Participantes

Financiación concedida El organismo FP7 notifico la concesión del proyecto el día 2019-02-28 No tenemos la información de la convocatoria

0% 100% 100%

Información adicional privada

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

2 Participantes

UOXF

0.00€ | Lider

UEDIN

N.D. | Participante

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

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

Complexity of CSPs Algorithms and Complexity of Constraint Satisfaction Problem... 160K€ Cerrado

PARAPPROX Parameterized Approximation 2M€ Cerrado

PARAPATH Parameterized Complexity Through the Lens of Path Problems 1M€ Cerrado

HOFGA The Hardness of Finding Good Algorithms 1M€ Cerrado

ACUITY Algorithms for coping with uncertainty and intractability 2M€ Cerrado

Líder del proyecto

THE CHANCELLOR MASTERS AND SCHOLARS OF THE UN... No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Presupuesto del proyecto 1M€

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

Descripción del proyecto One of the fundamental goals of theoretical computer science is to understand the possibilities and limits of efficient computation. This quest has two dimensions. The theory of algorithms focuses on finding efficient solutions to problems, while computational complexity theory aims to understand when and why problems are hard to solve. These two areas have different philosophies and use different sets of techniques. However, in recent years there have been indications of deep and mysterious connections between them. In this project, we propose to explore and develop the connections between algorithmic analysis and complexity lower bounds in a systematic way. On the one hand, we plan to use complexity lower bound techniques as inspiration to design new and improved algorithms for Satisfiability and other NP-complete problems, as well as to analyze existing algorithms better. On the other hand, we plan to strengthen implications yielding circuit lower bounds from non-trivial algorithms for Satisfiability, and to derive new circuit lower bounds using these stronger implications. This project has potential for massive impact in both the areas of algorithms and computational complexity. Improved algorithms for Satisfiability could lead to improved SAT solvers, and the new analytical tools would lead to a better understanding of existing heuristics. Complexity lower bound questions are fundamental but notoriously difficult, and new lower bounds would open the way to unconditionally secure cryptographic protocols and derandomization of probabilistic algorithms. More broadly, this project aims to initiate greater dialogue between the two areas, with an exchange of ideas and techniques which leads to accelerated progress in both, as well as a deeper understanding of the nature of efficient computation.

Conecta tu I+D

Entra hoy

¿Olvidé mi contraseña?

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores