Distributed and Dynamic Graph Algorithms and Complexity
This project aims to (i) resolve challenging graph problems in distributed and dynamic settings, with a focus on connectivity problems (such as computing edge connectivity and distances), and (ii) on the way develop a systematic a...
ver más
31/07/2022
UCPH
2M€
Presupuesto del proyecto: 2M€
Líder del proyecto
KOBENHAVNS UNIVERSITET
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.
¿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
Información proyecto DisDyn
Duración del proyecto: 68 meses
Fecha Inicio: 2016-11-28
Fecha Fin: 2022-07-31
Líder del proyecto
KOBENHAVNS UNIVERSITET
No se ha especificado una descripción o un objeto social para esta compañía.
TRL
4-5
Presupuesto del proyecto
2M€
Fecha límite de participación
Sin fecha límite de participación.
Descripción del proyecto
This project aims to (i) resolve challenging graph problems in distributed and dynamic settings, with a focus on connectivity problems (such as computing edge connectivity and distances), and (ii) on the way develop a systematic approach to attack problems in these settings, by thoroughly exploring relevant algorithmic and complexity-theoretic landscapes. Tasks include
- building a hierarchy of intermediate computational models so that designing algorithms and proving lower bounds can be done in several intermediate steps,
- explaining the limits of algorithms by proving conditional lower bounds based on old and new reasonable conjectures, and
- connecting techniques in the two settings to generate new insights that are unlikely to emerge from the isolated viewpoint of a single field.
The project will take advantage from and contribute to the developments in many young fields in theoretical computer science, such as fine-grained complexity and sublinear algorithms. Resolving one of the connectivity problems will already be a groundbreaking result. However, given the approach, it is likely that one breakthrough will lead to many others.