Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these propert...
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Article |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2104.04908 http://arxiv.org/abs/2104.04908 |
| Tags: |
Pas de tags, Soyez le premier à ajouter un tag!
|