4 papers
The Quantum Message Complexity of Distributed Wake-Up with Advice
Peter Robinson, Ming Ming Tan
We consider the distributed wake-up problem with advice, where nodes are equipped with initial knowledge about the network at large. After the adversary awakens a subset of nodes,…
Deterministic Lower Bounds for -Edge Connectivity in the Distributed Sketching Model
Peter Robinson, Ming Ming Tan
We study the -edge connectivity problem on undirected graphs in the distributed sketching model, where we have nodes and a referee. Each node sends a single message to the r…
Perfect Matching with Few Link Activations
Hugo Mirault, Peter Robinson, Ming Ming Tan +1
We consider the problem of computing a perfect matching problem in a synchronous distributed network, where the network topology corresponds to a complete bipartite graph. The comm…
Rise and Shine Efficiently! Tight Bounds for Adversarial Wake-up
Peter Robinson, Ming Ming Tan
We study the wake-up problem in distributed networks, where an adversary awakens a subset of nodes at arbitrary times, and the goal is to wake up all other nodes as quickly as poss…