Fall 2018

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Thursday, October 18th, 2018 11:30 am12:00 pm

Add to Calendar


Huacheng Yu (Harvard University)

Graph sketching is a powerful technique to probabilistically ``summarize'' a graph. It may be used to obtain streaming algorithm with low space usage for maintaining the connectivity of a graph, computing approximate minimum spanning forest, and to obtain communication efficient protocols for spanning forest [AGM'12], etc. In this talk, I will discuss the optimality of two of its applications: the space complexity of maintaining a spanning forest of a graph under edge insertion and deletion; the simultaneous communication complexity of spanning forest. The method of graph sketching solves the first problem with O(nlog^3 n) bits of space, and the latter with O(log^3 n) bits of communication per player. We show that both bounds cannot be improved for any streaming algorithm and communication protocol. Joint work with Jelani Nelson.