Theory Seminar

Lower bounds for estimating matching size in streaming models

Dawei HuangGraduate StudentUniversity of Michigan

In this talk I will survey computational limits in approximating size of maximum matchings in bipartite graph in various streaming model. I will introduce the Rusza-Szemeredi Graph, a graph that can be partitioned into large disjoint induced matchings and its application in deriving hard instances for streaming algorithm.

Sponsored by