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

DOI10.1145/3564246.3585192MaRDI QIDQ6499223zbMATH OpenFDO

Authors Sepehr Assadi, Janani Sundaresan

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585192

zbMATH Keywords

communication complexityconnected componentsgraph streamingrandom order streams

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• 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
• 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?)
• 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 complexity of approximating Max 2CSP and Max Acyclic Subgraph
• Streaming Lower Bounds for Approximating MAX-CUT
• 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

Cited in

(4)

• Streaming edge coloring with asymptotically optimal colors
• Weighted matching in the random-order streaming and robust communication models
• Sketching approximability of all finite CSPs
• Optimal communication complexity of chained index

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)