|
An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation| title | An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation |
|---|
| start_date | 2024/02/27 |
|---|
| schedule | 14h |
|---|
| online | no |
|---|
| location_info | Salle 3052 |
|---|
| summary | 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. |
|---|
| responsibles | Hamoudi |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2024/02/08 13:36 UTC |
| |
|