DIDYA studies how to design algorithms for networks that constantly change. From theory to foundations, we explore how dynamic networks compute, verify, and adapt.
The project is funded by the Agence nationale de la recherche (ANR) and led by Ami Paz.
We study several aspects of distributed dynamic systems. Below are some of the topics we are interested in, together with a few relevant publications.
E.g., dynamic-LOCAL and dynamic-CONGEST (classical graph algorithms with a dynamic twist).
Example. The network maintains an MIS, and then an edge is added between two MIS nodes—how long does it take to restore correctness?
Ensuring that a changing network maintains desired properties.
Example. Checking whether a network is bipartite requires global communication (e.g., to distinguish an odd cycle from an even one). However, giving each node a 0/1 certificate makes verification simple and local.
Distributed Non-Interactive Zero-Knowledge Proofs (with cryptography flavor)
Going beyond worst-case analysis of dynamic networks (with significant use of probability theory).
For problems that are hard in the worst case but easy on average: what happens in between?
Combinatorial topology has been used in shared-memory systems for decades; we extend these techniques to dynamic graph algorithms.