Demo Data from VLDB 2026 / reviewers in the wild / expert
Mars Xiang
dblp:437/6392
· DBLP profile ↗
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
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Approximation and online algorithms › approximation algorithms
approximation guarantees |
1.0 | 1 | 2026 | 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.0 | 1 | 2026 | Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints · STOC 2026 |
Computational complexity
lower bounds |
1.0 | 1 | 2026 | 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.0 | 1 | 2026 | 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.0 | 1 | 2026 | 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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via BlueprintsabstractIn 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 |
STOC | 3 |