ERC Starting Grant · 2016
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 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…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.