Cover Image

A New Information Complexity Measure for Multi-pass Streaming with Applications

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Braverman, Mark, Garg, Sumegha, Li, Qian, Wang, Shuo, Woodruff, David P., Zhang, Jiapeng
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

Online Learning with Limited Information in the Sliding Window Model
by: Braverman, Vladimir, et al.
Published: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Optimality of Frequency Moment Estimation
by: Braverman, Mark, et al.
Published: (2024)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Undirected Multicast Network Coding Gaps via Locally Decodable Codes
by: Braverman, Mark, et al.
Published: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Streaming Zero-Knowledge Proofs
by: Cormode, Graham, et al.
Published: (2023)

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

Parameterized Complexity of Streaming Diameter and Connectivity Problems
by: Oostveen, Jelle J., et al.
Published: (2022)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
by: Sharma, Amatya, et al.
Published: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
by: Chen, Xi, et al.
Published: (2026)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
by: Wang, Chengu
Published: (2026)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
by: Zhang, Bingwei, et al.
Published: (2026)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
by: Ene, Alina, et al.
Published: (2025)

Parameterized Complexity of Vehicle Routing
by: Döring, Michelle, et al.
Published: (2025)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

On the Complexity of Signed Roman Domination
by: Reddy, Sangam Balchandar
Published: (2025)

On the Space Complexity of Online Convolution
by: Andersson, Joel Daniel, et al.
Published: (2025)

Computational Complexity in Property Testing
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

The Complexity of Counting Small Sub-Hypergraphs
by: Bressan, Marco, et al.
Published: (2025)