Organizer(s):

Sepehr Assadi, Rutgers University

Swastik Kopparty, Rutgers University

Christian Konrad, University of Bristol

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.

The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home