Theory Seminar: Lower Bounds for Two-pass Streaming Algorithms for Maximum Matching

Abstract: In this talk, I will discuss a recent joint work with my PhD student Kheeran Naidu on lower bounds for the Maximum Matching problem in the semi-streaming model. In this model, an algorithm performs multiple passes over the edges of an input graph and is tasked with computing a matching that is as large as possible using space O(n polylog n), where n is the number of vertices of the input graph.

We will focus on the two-pass setting, and we show that every randomized two-pass streaming algorithm that computes a better than 8/9-approximation to Maximum Matching requires strictly more than semi-streaming space.

Prior to our work, only a conditional two-pass lower bound by Assadi [SODA’22] was known that relates the quality of their lower bound to the maximum density of Ruzsa-Szemeredi graphs (RS-graphs) with matchings of linear sizes. In the best case, i.e., if very dense RS-graphs with linear-sized matchings exist, their lower bound rules out approximation ratios above 0.98, however, with current knowledge, only approximation factors of 1 − o(1) are ruled out.

Our lower bound makes use of the information cost trade-off of the Index problem in the two-party communication setting established by Jain et al. [JACM’09]. To the best of our knowledge, our work is the first that exploits this trade-off result in the context of lower bounds for multi-pass graph streaming algorithms.

Bio: Christian Konrad is a Senior Lecturer (equivalent to Associate Professor in the North American system) at the University of Bristol, UK. Prior to joining Bristol, he held postdoctoral positions at the University of Warwick and the University of Reykjavik. He obtained a PhD from the University of Paris Diderot and a Master’s degree in Computer Science with Mathematics from the Technical University of Munich. His research focus is algorithms theory, in particular, data streaming algorithms, communication complexity, and distributed computation. His work is currently supported by an EPSRC New Investigator Award. He is the head of the algorithms research group at Bristol and acts as the Programme Director of the joint honours Mathematics and Computer Science degree.