Theory Seminar: Sepehr Assadi

We are excited to announce that this week’s speaker is Sepehr Assadi. The talk will take place on Friday, 3/3 at 1pm in Levine 307.

Title: An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams

Abstract: We present an algorithm for the maximum matching problem in dynamic (insertion-deletions) streams with asymptotically optimal space complexity: for any n-vertex graph, our algorithm with high probability outputs an α-approximate matching in a single pass using O(n^2/α^3) bits of space.

A long line of work on the dynamic streaming matching problem has reduced the gap between space upper and lower bounds first to n^o(1) factors [Assadi-Khanna-Li-Yaroslavtsev; SODA 2016] and subsequently to polylog(n) factors [Dark-Konrad; CCC 2020]. Our upper bound now matches the Dark-Konrad lower bound asymptotically, thus completing this research direction.