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

Cites Work

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

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)