On the communication and streaming complexity of maximum bipartite matching¶
Goel, K., Kapralov, M., & Khanna, S. (2012). On the communication and streaming complexity of maximum bipartite matching. ACM.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Domain-specific¶
- Ruzsa–Szemerédi Problem
- Dense Ruzsa–Szemerédi graphs provide hard communication instances and govern bounds for graph-streaming matching approximations
This sourceShows that the smallest epsilon-matching cover of a graph is essentially the size of the largest epsilon-Ruzsa-Szemeredi graph on the same vertex set, and uses that to prove superlinear communication and one-pass streaming lower bounds for better-than-2/3 bipartite matching approximation.
SupportedVerified against the source
- Dense Ruzsa–Szemerédi graphs provide hard communication instances and govern bounds for graph-streaming matching approximations
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 1 of 1 citation: 1 supported. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:a25e24472d85 · see in the full table