Communication Complexity of Statistical Distance

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.49zbMath1467.68056OpenAlexW2753650780MaRDI QIDQ5002655

No author found.

Publication date: 28 July 2021

Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.49

zbMATH Keywords

communication complexitystatistical distance

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of estimating min-entropy
• A discrepancy lower bound for information complexity
• An Interactive Information Odometer and Applications
• On the Complexity of Computational Problems Regarding Distributions
• A Counterexample to Strong Parallel Repetition
• Parallel Repetition in Projection Games and a Concentration Bound
• Testing Symmetric Properties of Distributions
• Big Data on the Rise?
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Interactive Information Complexity
• Approximation algorithms for classification problems with pairwise relationships
• A complete problem for statistical zero knowledge
• The Complexity of Distinguishing Markov Random Fields
• An Approximate L¹ -Difference Algorithm for Massive Data Streams
• Communication Complexity
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Testing Closeness of Discrete Distributions
• Rectangles Are Nonnegative Juntas

This page was built for publication: Communication Complexity of Statistical Distance