The Communication Complexity of Distributed epsilon-Approximations
From MaRDI portal
Publication:4978194
DOI10.1137/16M1093604zbMath1371.68318OpenAlexW2742707984MaRDI QIDQ4978194
Publication date: 18 August 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1093604
Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Range counting over multidimensional data streams
- Tight upper bounds for the discrepancy of half-spaces
- Concentration of measure and isoperimetric inequalities in product spaces
- Geometric methods in the study of irregularities of distribution
- Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy
- Mergeable summaries
- Deterministic sampling and range counting in geometric data streams
- Constructive Discrepancy Minimization by Walking on the Edges
- On a theorem of Beck
- Communication Complexity
- Factorization Norms and Hereditary Discrepancy
- An Optimal Lower Bound for Distinct Elements in the Message Passing Model
- Interactive information complexity
- Tight bounds for distributed functional monitoring
- Elements of Information Theory
- On Range Searching in the Group Model and Combinatorial Discrepancy
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Generalization of a Probability Limit Theorem of Cramer
- Concentration of Measure for the Analysis of Randomized Algorithms
- Geometric discrepancy. An illustrated guide
- Improved bounds on the sample complexity of learning
This page was built for publication: The Communication Complexity of Distributed epsilon-Approximations
