On Arthur Merlin Games in Communication Complexity

Abstract

We show several results related to interactive proof modes of communication complexity. First we show lower bounds for the QMA-communication complexity of the functions Inner Product and Disjointness. We describe a general method to prove lower bounds for QMA-communication complexity, and show how one can 'transfer' hardness under an analogous measure in the query complexity model to the communication model using Sherstov's pattern matrix method. Combining a result by Vereshchagin and the pattern matrix method we find a communication problem with AM-communication complexity $O(\log n)$, PP-communication complexity $\Omega (n^{1/3})$, and QMA-communication complexity $\Omega (n^{1/6})$. Hence in the world of communication complexity noninteractive quantum proof systems are not able to efficiently simulate co-nondeterminism or interaction. These results imply that the related questions in Turing machine complexity theory cannot be resolved by 'algebrizing' techniques. Finally we show that in MA-protocols there is an exponential gap between one-way protocols and two-way protocols (this refers to the interaction between Alice and Bob). This is in contrast to nondeterministic, AM-, and QMA-protocols, where one-way communication is essentially optimal.

19 pages

References in corpus (1)

• Quantum communication complexity of symmetric predicates

Cited by in corpus (6)

• Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication
• Faster Private Release of Marginals on Small Databases
• The layer complexity of Arthur-Merlin-like communication
• Streaming Verification in Data Analysis
• Two Results about Quantum Messages
• Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity