Seminar Details
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graphs
- Start Date: December 9, 2020
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Organizers: Sepehr Assadi || Swastik Kopparty
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Christian Konrad - University of Bristol
- Event Location: Online Event
- Event Additional Info: <p>The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p> </p> <p>See: <a href="https://sites.google.com/view/dimacs-theory-seminar/home">https://sites.google.com/view/dimacs-theory-seminar/home</a></p> <p> </p>
- Presentation Type: Stand Alone Presentation
- Abstract:
Abstract: In this talk, I will discuss simple optimal lower bounds on the one-way two-party communication complexity of approximate Maximum Matching and Minimum Vertex Cover with deletions. In this model, Alice holds a set of edges and sends a single message to Bob. Bob holds a set of edge deletions, which form a subset of Alice's edges, and needs to report a large matching or a small vertex cover in the graph spanned by the edges that are not deleted. Our results imply optimal space lower bounds for insertion-deletion streaming algorithms for Maximum Matching and Minimum Vertex Cover. An optimal space lower bound for Maximum Matching was previously given by Assadi et al. [SODA 2016], however, this lower bound only holds for the subclass of streaming algorithms that are able to process very long (at least triple exponential in n) input streams. This work appeared at CCC'20. Joint work with Jacques Dark.