No article text was recorded for this version.
multi-pass streaming complexity
Version 1 of 167 papers83 conceptsfrozen 2026-10-04
Papers in this version
- Blog: Towards Tight Bounds for the Streaming Set Cover Problem
- Blog: Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams
- Blog: A New Information Complexity Measure for Multi-pass Streaming with Applications
- Blog: Streaming Algorithms for Support-Aware Histograms
- Blog: Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem
- Blog: Strong Memory Lower Bounds for Learning Natural Models
- Blog: Strong Memory Lower Bounds for Learning Natural Models
- Blog: Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
- Blog: Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
- Blog: New Characterizations in Turnstile Streams with Applications
- Blog: Space Lower Bounds for Graph Stream Problems
- Blog: A Two-Pass Lower Bound for Semi-Streaming Maximum Matching
- Blog: (Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
- Blog: Counting Simplices in Hypergraph Streams
- Blog: Strong Memory Lower Bounds for Learning Natural Models
- Blog: Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
- Blog: Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
- Blog: New Streaming Algorithms for High Dimensional EMD and MST
- Blog: Noisy Boolean Hidden Matching with Applications
- Blog: Approximately Counting Subgraphs in Data Streams
- Blog: Polynomial Pass Lower Bounds for Graph Streaming Algorithms
- Blog: John Ellipsoids via Lazy Updates
- Blog: True Randomness from Big Data
- Blog: Sketches for Matrix Norms: Faster, Smaller and More General
- Blog: Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model
- Blog: Communication and Memory Efficient Testing of Discrete Distributions
- Blog: Pseudo-deterministic Streaming
- Blog: Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model
- Blog: Strong Memory Lower Bounds for Learning Natural Models
- Blog: Streaming Submodular Maximization Under Matroid Constraints
- Blog: Sliding window order statistics in sublinear space
- Blog: Low Rank Approximation Lower Bounds in Row-Update Streams
- Blog: Streaming and Communication Complexity of Load-Balancing via Matching Contractors
- Blog: Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
- Blog: Streaming Euclidean k-median and k-means with o(log n) Space
- Blog: Streaming Algorithms For ℓp Flows and ℓp Regression
- Blog: Classification of the streaming approximability of Boolean CSPs
- Blog: Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance
- Blog: Multi-Pass Streaming Lower Bounds for Uniformity Testing
- Blog: Better Bounds for Frequency Moments in Random-Order Streams
- Blog: An Optimal Space Lower Bound for Approximating MAX-CUT
- Blog: Streaming Algorithms for Support-Aware Histograms
- Blog: Streaming Facility Location in High Dimension via Geometric Hashing
- Blog: Streaming Lower Bounds for Approximating MAX-CUT
- Blog: Approximate Maximum Matching in Random Streams
- Blog: Parameterized Streaming Algorithms for Min-Ones d-SAT
- Blog: High-Dimensional Geometric Streaming in Polynomial Space
- Blog: The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
- Blog: A New Information Complexity Measure for Multi-pass Streaming with Applications
- Blog: Approximate Convex Hull of Data Streams
- Blog: Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model
- Blog: Testable algorithms for approximately counting edges and triangles in sublinear time and space
- Blog: Sketching Cuts in Graphs and Hypergraphs
- Blog: Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
- Blog: Linear Space Streaming Lower Bounds for Approximating CSPs
- Blog: An optimal space lower bound for approximating MAX-CUT
- Blog: Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
- Blog: Separations for Estimating Large Frequency Moments on Data Streams
- Blog: Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
- Blog: Almost Optimal Streaming Algorithms for Coverage Problems
Showing 60 of 67 papers.
History & citation
Current · Permanent link
- Pass Complexity in Streaming Graph Algorithms merged into this direction (90% overlap)
- Memory Efficiency Gaps in Multi-Pass Streaming Algorithms merged into this direction (77% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_multi_pass_streaming_complexity_5c8496a9,
title = {multi-pass streaming complexity},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/multi-pass-streaming-complexity/rdr_5c8496a97174451299745dc6dfc6e18f},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}This exact version (version 1, frozen text):
@misc{lacuna_multi_pass_streaming_complexity_5c8496a9_v1,
title = {multi-pass streaming complexity},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/multi-pass-streaming-complexity/rdr_5c8496a97174451299745dc6dfc6e18f/v/1},
note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}