# Beating Two-Thirds For Random-Order Streaming Matching

arXiv: https://arxiv.org/abs/2102.07011 · HTML: https://mlsanity.com/paper/2102.07011/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2021.

## Built on by (most cited first, 1 of 1)

- [Stochastic Matching via Local Sparsification](https://mlsanity.com/paper/2605.14195/) (2026)

## Abstract (arXiv)

We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary n-vertex graph G=(V, E) arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use n · poly(log n) space, and output a large matching of G. We prove that for an absolute constant ε0 > 0, one can find a (2/3 + ε0)-approximate maximum matching of G using O(n log n) space with high probability. This breaks the natural boundary of 2/3 for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a (2/3 + Omega(1))-approximation is achievable.