Problem 65: Communication Complexity of Connectivity
Revision as of 04:18, 4 June 2014 by Krzysztof Onak (talk | contribs)
| Suggested by | Andrew McGregor |
|---|---|
| Source | Bertinoro 2014 |
| Short link | https://sublinear.info/65 |
In the sketch-based algorithms for connectivity on a graph, the procedure works as follows. Each vertex prepares a $O(\log^3n)$-sized sketch describing its neighborhood, and sends it to a controller. Each node has access to a public shared random source to compute this sketch.
Can we reduce the number of bits required by each node? Can it be made as small a $O(\log^2 n)$ or $O(\log n)$?
