Abstract
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.