C&O Reading Group - Parth Mittal

Title: Nearly optimal communication and query complexity of bipartite matching

Abstract: I will talk about a recent paper (Blikstad, van den Brand, Efron, Mukhopadhyay, Nanongkai, FOCS 22) which gives near-optimal algorithms for bipartite matching (and several generalizations) in communication complexity, and several types of query complexity. We will focus only on the simplest case (i.e. unweighted bipartite matching), and will not assume any background on communication or query complexity.