6 papers
Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction
Peter Robinson, Ming Ming Tan
We present the first polynomial lower bounds for several fundamental problems in the distributed graph sketching model in the tiny-error regime, which includes deterministic algori…
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…
Tight Bounds on the Message Complexity of Distributed Tree Verification
Shay Kutten, Peter Robinson, Ming Ming Tan
We consider the message complexity of verifying whether a given subgraph of the communication network forms a tree with specific properties both in the KT- (nodes know their …