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.
30-11-2024:
Cataluña Gestión For...
Se ha cerrado la línea de ayuda pública: Gestión Forestal Sostenible para Inversiones Forestales Productivas para el organismo:
29-11-2024:
IDAE
En las últimas 48 horas el Organismo IDAE ha otorgado 4 concesiones
29-11-2024:
ECE
En las últimas 48 horas el Organismo ECE ha otorgado 2 concesiones
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.
Seleccionando "Aceptar todas las cookies" acepta el uso de cookies para ayudarnos a brindarle una mejor experiencia de usuario y para analizar el uso del sitio web. Al hacer clic en "Ajustar tus preferencias" puede elegir qué cookies permitir. Solo las cookies esenciales son necesarias para el correcto funcionamiento de nuestro sitio web y no se pueden rechazar.
Cookie settings
Nuestro sitio web almacena cuatro tipos de cookies. En cualquier momento puede elegir qué cookies acepta y cuáles rechaza. Puede obtener más información sobre qué son las cookies y qué tipos de cookies almacenamos en nuestra Política de cookies.
Son necesarias por razones técnicas. Sin ellas, este sitio web podría no funcionar correctamente.
Son necesarias para una funcionalidad específica en el sitio web. Sin ellos, algunas características pueden estar deshabilitadas.
Nos permite analizar el uso del sitio web y mejorar la experiencia del visitante.
Nos permite personalizar su experiencia y enviarle contenido y ofertas relevantes, en este sitio web y en otros sitios web.