Date: September 28, 2026
Title: Greedy is Optimal for the Semi-Streaming Matching Problem
Speaker: Sepehr Assadi, Associate Professor, Cheriton School of Computer Science, Waterloo University
Abstract: We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering a longstanding open question in graph streaming literature since the introduction of the model. Our proof consists of two main parts:
1. Blueprint framework: reducing the problem of proving lower bounds for semi-streaming matching to constructing certain combinatorial objects which we call blueprints; and,
2. Blueprint construction: an optimal construction of such blueprints usable within this framework.
Putting these two parts together then implies our semi-streaming matching lower bound.
Based on joint work with Max Jiang and Mars Xiang in https://arxiv.org/pdf/2607.14644 (STOC 2026) and https://arxiv.org/abs/2607.14656 (arXiv; July 2026)