Theory Seminar

Lower bounds for estimating matching size in streaming models

Dawei Huang

Graduate Student
University of Michigan
Tuesday, February 07, 2017
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

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.

Additional Information

Sponsor(s): CSE

Open to: Public