A direct product theorem for two-party bounded-round public-coin communication complexity

DOI10.1007/S00453-015-0100-0zbMath1353.68085OpenAlexW2277697754MaRDI QIDQ343852

Attila Pereszlényi, Rahul Jain, Penghui Yao

Publication date: 29 November 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0100-0

zbMATH Keywords

information theorycommunication complexitystrong direct product theorem

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Superlinear lower bounds for multipass graph processing ⋮ Towards a reverse Newman's theorem in interactive information complexity ⋮ Certifying equality with limited interaction ⋮ A strong direct product theorem for quantum query complexity ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Simulation theorems via pseudo-random properties ⋮ Lifting Theorems for Equality ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ A parallel repetition theorem for entangled projection games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strong direct product theorem for quantum query complexity
• An information statistics approach to data stream and communication complexity
• Improved direct product theorems for randomized query complexity
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• Robustness of quantum Markov chains
• On the distributional complexity of disjointness
• Towards proving strong direct product theorems
• New Strong Direct Product Results in Communication Complexity
• How to Compress Interactive Communication
• A strong direct product theorem for disjointness
• An Interactive Information Odometer and Applications
• Information Equals Amortized Communication
• On quantum and probabilistic communication
• Products and Help Bits in Decision Trees
• A Parallel Repetition Theorem
• Communication Complexity
• Strong Direct Product Theorems for Quantum Communication and Query Complexity
• Interaction in quantum communication and the complexity of set disjointness
• Direct Product via Round-Preserving Compression
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Elements of Information Theory
• Information Equals Amortized Communication
• The communication complexity of pointer chasing

This page was built for publication: A direct product theorem for two-party bounded-round public-coin communication complexity