Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
Sepehr Assadi, Gillat Kol, Rotem Oshman · 2020
Consider the following distributed graph sketching model: There is a referee and n vertices in an undirected graph G sharing public randomness. Each vertex v only knows its neighborhood in G and the referee receives no input initially. The vertices simultaneously each sends a message, called a sketch, to the referee who then based on the received sketches outputs a solution to some combinatorial problem on G, say, the minimum spanning tree problem.