The Simultaneous Communication of Disjointness with Applications to Data Streams

DOI10.1007/978-3-662-47672-7_88zbMath1440.68094OpenAlexW2401312511MaRDI QIDQ3448862

Omri Weinstein, David P. Woodruff

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_88

zbMATH Keywords

information theoryinformation complexityfrequency momentsmultiparty communication complexity

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Communication complexity, information complexity (68Q11)

Related Items (7)

Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Unnamed Item ⋮ High Probability Frequency Moment Sketches ⋮ Public vs. private randomness in simultaneous multi-party communication complexity ⋮ Unnamed Item ⋮ Public vs. Private Randomness in Simultaneous Multi-party Communication Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• The space complexity of approximating the frequency moments
• The Fast Cauchy Transform and Faster Robust Linear Regression
• Approximating Large Frequency Moments with Pick-and-Drop Sampling
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
• An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits
• Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming
• Space lower bounds for distance approximation in the data stream model
• Optimal approximations of the frequency moments of data streams
• Simpler algorithm for estimating frequency moments of data streams
• The Probabilistic Communication Complexity of Set Intersection
• Information Lower Bounds via Self-reducibility
• Turnstile streaming algorithms might as well be linear sketches
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Tight Lower Bound for Linear Sketches of Moments
• Tight bounds for distributed functional monitoring
• Subspace embeddings for the L ₁ -norm with applications
• Streaming Algorithms via Precision Sampling
• Communication Lower Bounds Using Directional Derivatives

This page was built for publication: The Simultaneous Communication of Disjointness with Applications to Data Streams