Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Mars Xiang

dblp:437/6392 · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
1since 2021 · last 2026
0009-0001-1404-7358ORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Graph algorithms and graph theory · 40% Algorithms and data structures · 20% Computational complexity · 20%

Topics — the 5 heaviest of 5, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Approximation and online algorithms › approximation algorithms
approximation guarantees
1.012026
Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints · STOC 2026
Graph algorithms and graph theory
graph matching
1.012026
Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints · STOC 2026
Computational complexity
lower bounds
1.012026
Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints · STOC 2026
Graph algorithms and graph theory › graph matching
maximum matching
1.012026
Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints · STOC 2026
Algorithms and data structures › data streams
streaming algorithms
1.012026
Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints · STOC 2026

Methods — techniques the papers use, named apart from their topics

information-theoretic argument · 1.0extremal graph theory · 1.0blueprint framework · 1.0
YearPublicationVenuePosition
2026 Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints
abstract
In the semi-streaming model, we have an $n$-vertex graph $G=(V,E)$ whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, use a limited memory of $\tilde O(n)$ bits, and output a solution to the problem at hand at the end. A central open question in this area is to determine the best approximation ratio possible for the maximum matching problem via single-pass semi-streaming algorithms. This problem admits a simple $0.5$-approximation algorithm, by maintaining a maximal matching greedily, which, despite extensive efforts, has remained the state of the art. Lower bounds for this problem have also been few and far between with best known bounds ruling out better than $1/(1+\ln{(2)}) \sim 0.590$ approximation, using a highly complicated construction motivated by the literature on RS graphs from extremal graph theory. We develop a new framework for proving lower bounds for the semi-streaming matching problem. Our framework abstracts out the extremal graph theory and information theoretic arguments in the lower bounds, and reduces the problem to constructing certain constant-size graphs, which we call blueprints. Not only existing lower bounds can be captured by these blueprints, leading to far simpler and more concise arguments, but also we can design new blueprints that can be used to rule out $(8-2\sqrt{10})/3 \sim 0.558$-approximation for the semi-streaming matching problem. We believe this approach can be of its own independent interest and lead to further improvements on this tantalizing open question.
Sepehr Assadi, Max Jiang, Mars Xiang
STOC3