The Simultaneous Communication of Disjointness with Applications to Data Streams
From MaRDI portal
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Communication complexity, information complexity (68Q11) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
Recommendations
- scientific article; zbMATH DE number 7711619
- The randomized communication complexity of set disjointness
- The multiparty communication complexity of set disjointness
- The multiparty communication complexity of set disjointness
- An information statistics approach to data stream and communication complexity
- Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
- The communication complexity of multiparty set disjointness under product distributions
- Simplified lower bounds on the multiparty communication complexity of disjointness
- Beyond set disjointness: the communication complexity of finding the intersection
- Robust lower bounds for communication and stream computation
Cites work
- 1-pass relative-error L_p-sampling with applications
- A Tight Lower Bound for High Frequency Moment Estimation with Small Error
- An improved data stream algorithm for frequency moments
- An information statistics approach to data stream and communication complexity
- An optimal algorithm for large frequency moments using \(O(n^{1-2/k})\) bits
- Approximating Large Frequency Moments with Pick-and-Drop Sampling
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Communication lower bounds using directional derivatives
- Information complexity versus corruption and applications to orthogonality and gap-Hamming
- Information Lower Bounds via Self-reducibility
- On the exact space complexity of sketching and streaming small norms
- Optimal approximations of the frequency moments of data streams
- Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
- Optimal space lower bounds for all frequency moments
- Simpler algorithm for estimating frequency moments of data streams
- Space lower bounds for distance approximation in the data stream model
- Streaming algorithms via precision sampling
- Subspace embeddings for the L 1 -norm with applications
- The Probabilistic Communication Complexity of Set Intersection
- The space complexity of approximating the frequency moments
- Tight bounds for distributed functional monitoring
- Tight lower bound for linear sketches of moments
- Turnstile streaming algorithms might as well be linear sketches
Cited in
(13)- Public vs. private randomness in simultaneous multi-party communication complexity
- Robust lower bounds for communication and stream computation
- Public vs. private randomness in simultaneous multi-party communication complexity
- High probability frequency moment sketches
- Separating \(k\)-player from \(t\)-player one-way communication, with applications to data streams
- scientific article; zbMATH DE number 7250148 (Why is no real title available?)
- An optimal lower bound for distinct elements in the message passing model
- Lower bounds for multi-pass processing of multiple data streams
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- scientific article; zbMATH DE number 7650118 (Why is no real title available?)
- An information statistics approach to data stream and communication complexity
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Separating k-player from t-player one-way communication, with applications to data streams
This page was built for publication: The Simultaneous Communication of Disjointness with Applications to Data Streams
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448862)
