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

DOI10.1145/3564246.3585192MaRDI QIDQ6499223

Janani Sundaresan, Sepehr Assadi

Publication date: 8 May 2024

zbMATH Keywords

connected componentscommunication complexitygraph streamingrandom order streams

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graph problems in a semi-streaming model
• Sketching Cuts in Graphs and Hypergraphs
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• Exponential separation of quantum and classical one-way communication complexity
• Graph Distances in the Data-Stream Model
• Planar Matching in Streams Revisited
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
• Testable bounded degree graph properties are random order streamable
• The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
• Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
• On approximating functions of the singular values in a stream
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Streaming Lower Bounds for Approximating MAX-CUT
• Approximating matching size from random streams
• The Factorization of Linear Graphs
• Concentration of Measure for the Analysis of Randomized Algorithms
• 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