No article text was recorded for this version.
communication complexity reduction
Version 2 of 2145 papers176 conceptsfrozen 2026-10-04
Papers in this version
- Blog: On the Amortized Complexity of Approximate Counting
- Blog: Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams
- Blog: Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams
- Blog: Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
- Blog: Query Complexity of Global Minimum Cut
- Blog: Stochastic Streams: Sample Complexity vs. Space Complexity
- Blog: Approximating Local Graph Structure in Almost Random Order Streams
- Blog: Ruling Sets in Random Order and Adversarial Streams
- Blog: Some Bounds on Communication Complexity of Gap Hamming Distance
- Blog: Communication Complexity (for Algorithm Designers)
- Blog: Tight Bounds for Graph Problems in Insertion Streams
- Blog: Sketching Approximability of All Finite CSPs
- Blog: On the amortized complexity of approximate counting
- Blog: The Learning and Communication Complexity of Subsequence Containment
- Blog: Mimicking Networks and Succinct Representations of Terminal Cuts
- Blog: Low Rank Approximation Lower Bounds in Row-Update Streams
- Blog: Keeping a Secret Requires a Good Memory: Unconditional Streaming Lower-Bounds for Differentially Private Algorithms
- Blog: Lower bounds for predecessor searching in the cell probe model
- Blog: Lower Bounds for Approximating Graph Parameters via Communication Complexity
- Blog: DecreaseKeys are expensive for external memory priority queues
- Blog: One-way Communication Complexity of Minimum Vertex Cover in General Graphs
- Blog: Towards a Theory of Parameterized Streaming Algorithms
- Blog: Space Lower Bounds for Graph Stream Problems
- Blog: Sliding Bloom Filters
- Blog: Streaming Lower Bounds and Asymmetric Set-Disjointness
- 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: Understanding the hardness of approximate query processing with joins
- Blog: O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set
- Blog: How Hard Is Counting Triangles in the Streaming Model?
- Blog: Tight Bounds for Distributed Functional Monitoring
- Blog: Improved lower bounds for matchings in the streaming model
- Blog: A Simple Proof of a New Set Disjointness with Applications to Data Streams
- Blog: Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams
- Blog: Separations and equivalences between turnstile streaming and linear sketching
- Blog: Noisy Boolean Hidden Matching with Applications
- Blog: Zero-one frequency laws
- Blog: Optimal Streaming Approximations for all Boolean Max-2CSPs
- Blog: Towards Optimal Moment Estimation in Streaming and Distributed Models
- Blog: Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
- Blog: Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding
- Blog: The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
- Blog: Space-Round Tradeoffs for MapReduce Computations
- Blog: A General Characterization of the Statistical Query Complexity
- Blog: RNNs can generate bounded hierarchical languages with optimal memory
- Blog: Polynomial Pass Lower Bounds for Graph Streaming Algorithms
- Blog: On Approximating Functions of the Singular Values in a Stream
- Blog: Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter
- Blog: Pseudo-deterministic Streaming
- Blog: The White-Box Adversarial Data Stream Model
- Blog: Are We Still Missing an Item?
- Blog: Better Bounds for Semi-Streaming Single-Source Shortest Paths
- Blog: Tight Network Topology Dependent Bounds on Rounds of Communication
- Blog: Sketching information divergences
- Blog: Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
- Blog: Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity
- Blog: Frequency Estimation with One-Sided Error
- Blog: Sketching Cuts in Graphs and Hypergraphs
- Blog: Lower Bounds for Adaptive Sparse Recovery
- Blog: Optimal Function Computation in Directed and Undirected Graphs
Showing 60 of 145 papers.
History & citation
Current · Permanent link
- non-adaptive update constraints split from this direction (50% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_communication_complexity_reduction_ac5c9197,
title = {communication complexity reduction},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/communication-complexity-reduction/rdr_ac5c9197d98146fc903ecf9a49dc52de},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}This exact version (version 2, frozen text):
@misc{lacuna_communication_complexity_reduction_ac5c9197_v2,
title = {communication complexity reduction},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/communication-complexity-reduction/rdr_ac5c9197d98146fc903ecf9a49dc52de/v/2},
note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}