Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DISTRIBUTED SKETCHING:
Reports tagged with distributed sketching:
TR22-136 | 21st September 2022
Sepehr Assadi, Gillat Kol, Zhijun Zhang

Rounds vs Communication Tradeoffs for Maximal Independent Sets

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both ... more >>>




ISSN 1433-8092 | Imprint