Difference between revisions of "Open Problems:65"
(Created page with "{{Header |title=Communication Complexity of Connectivity |source=bertinoro14 |who=Andrew McGregor }} ???") |
|||
| Line 4: | Line 4: | ||
|who=Andrew McGregor | |who=Andrew McGregor | ||
}} | }} | ||
| − | ??? | + | In the sketch-based algorithms for connectivity on a graph, the procedure works as follows. Each vertex prepares a $\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 ? To $\log^2 n$ ? To $\log n$ ? | ||
Revision as of 21:43, 28 May 2014
| 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 $\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 ? To $\log^2 n$ ? To $\log n$ ?
