Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model

Peter Robinson, Ming Ming Tan

We study the $k$-edge connectivity problem on undirected graphs in the distributed sketching model, where we have $n$ nodes and a referee. Each node sends a single message to the r…