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
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
