Greedy is Optimal for the Semi-Streaming Matching Problem
November 6, 2026 (1pm, GHC 8102 - part of the Theory Seminar series)

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 implies our semi-streaming matching lower bound.

Based on joint work with Max Jiang and Mars Xiang in https://arxiv.org/abs/2607.14644 (STOC 2026) and https://arxiv.org/abs/2607.14656 (arXiv; July 2026)