New Strong Direct Product Results in Communication Complexity
From MaRDI portal
Publication:2796407
DOI10.1145/2699432zbMath1333.68106OpenAlexW2205302211MaRDI QIDQ2796407
Publication date: 24 March 2016
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2699432
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Information theory (general) (94A15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (5)
A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Direct sum fails for zero-error average communication ⋮ Simulation theorems via pseudo-random properties ⋮ Unnamed Item ⋮ Lifting Theorems for Equality
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An information statistics approach to data stream and communication complexity
- Private vs. common random bits in communication complexity
- On the distributional complexity of disjointness
- Towards proving strong direct product theorems
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- How to compress interactive communication
- A strong direct product theorem for disjointness
- An Interactive Information Odometer and Applications
- A Parallel Repetition Theorem
- Communication Complexity
- Strong Direct Product Theorems for Quantum Communication and Query Complexity
- Direct Product via Round-Preserving Compression
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- A Parallel Approximation Algorithm for Positive Semidefinite Programming
- Information Equals Amortized Communication
This page was built for publication: New Strong Direct Product Results in Communication Complexity
