Research

As is by convention in theoretical computer science, authors are listed in alphabetical order of last name.

• Semi-Streaming Matching in a Single Pass II: Greedy is Optimal
  Sepehr Assadi, Max Jiang, Mars XiangarXiv 2026
  [arXiv] [Notes]
  Summary: We build on our earlier blueprint framework to prove that no single-pass semi-streaming algorithm for the maximum (bipartite) matching problem can achieve an approximation ratio better than half. In other words, the naive greedy algorithm is optimal for this problem. This fully resolves one of the most central open questions in the graph streaming literature dating back to the introduction of the model two decades ago.
• Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints
  Sepehr Assadi, Max Jiang, Mars XiangSTOC 2026
  [arXiv] [STOC]
  Summary: We reduce the problem of proving single-pass semi-streaming lower bounds for the maximum matching problem—one of the most longstanding open questions in the graph streaming literature—to a constant-size optimization problem which we call a “blueprint”. This allows one to bypass all information theory and extremal graph theory (in particular RS graphs) arguments needed in prior work and focus solely on constructing better blueprints. We then use blueprints to improve prior best lower bound of 0.59-approximation in [Kap21] to a 0.55-approximation (bonus: the paper is <1/3 in length).