New Strong Direct Product Results in Communication Complexity

DOI10.1145/2699432zbMath1333.68106OpenAlexW2205302211MaRDI QIDQ2796407

Rahul Jain

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

zbMATH Keywords

information theorycommunication complexitystrong direct product

Mathematics Subject Classification ID

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