Seminar • Algorithms and Complexity • Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings

Please note: This seminar will take place in M3 4206 and online.

Sepehr Assadi, Associate Professor
David R. Cheriton School of Computer Science

A semi-streaming (graph) algorithm processes its input graph by making one or a few passes over its edges and using a space proportional to the number of vertices, hence, (potentially) quadratically smaller than the input size. Semi-streaming algorithms have been at the forefront of theoretical research on processing massive graphs in recent years. In this talk, we will consider the maximum (bipartite) matching problem in the semi-streaming model.

There is a large body of semi-streaming algorithms for the maximum matching problem, developed over the last two decades, that achieve a (1+eps)-approximation in progressively smaller number of passes as a function of eps and size of the graph. In sharp contrast to this progress however, there is scarcely any lower bounds known for this problem, beyond single-pass and very recently two-pass algorithms. For instance, it is not even ruled out whether one can achieve a (1+eps)-approximation in a fixed constant number of passes, say, even three passes.

In this talk, we present the first pass-approximation tradeoff for (small) constant-factor approximation of semi-streaming matchings: semi-streaming (1-ε)-approximation of bipartite matching (even its size) requires Omega(log(1/ε)) passes under a natural combinatorial hypothesis that moderately dense Ruzsa-Szemeredi graphs do exist. The key to our analysis is a novel way of analyzing communication complexity of hiding permutations directly, instead of relying on tools from Boolean function analysis of prior work in this context. This maybe of its own independent interest.

The talk will be self-contained and no prior background in streaming algorithms or communication complexity will be needed to enjoy this talk.

This is joint work with Janani Sundaresan (to appear in FOCS 2023).

To attend this seminar in person, please go to M3 4206. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/96241178286.