(Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond

Cites work

scientific article; zbMATH DE number 3698383 (Why is no real title available?)
scientific article; zbMATH DE number 1256715 (Why is no real title available?)
scientific article; zbMATH DE number 1756011 (Why is no real title available?)
scientific article; zbMATH DE number 819814 (Why is no real title available?)
scientific article; zbMATH DE number 5485578 (Why is no real title available?)
scientific article; zbMATH DE number 7650072 (Why is no real title available?)
A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
Approximating matching size from random streams
Concentration of Measure for the Analysis of Randomized Algorithms
Data streams: algorithms and applications.
Dynamic graph stream algorithms in \(o(n)\) space
Estimating graph parameters from random order streams
Exponential separation of quantum and classical one-way communication complexity
Exponential separations for one-way quantum communication complexity, with applications to cryptography
Graph Distances in the Data-Stream Model
Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
On approximating functions of the singular values in a stream
On graph problems in a semi-streaming model
Planar matching in streams revisited
Sketching cuts in graphs and hypergraphs
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Stochastic streams: sample complexity vs. space complexity
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
Streaming Lower Bounds for Approximating MAX-CUT
Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
Sublinear estimation of weighted matchings in dynamic data streams
Testable bounded degree graph properties are random order streamable
The Factorization of Linear Graphs
The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
The streaming complexity of cycle counting, sorting by reversals, and other problems

This page was built for publication: (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499223)