Problem 65: Communication Complexity of Connectivity

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$ ?