Delegating all of the work to the prover in $\mathcal{MA}$ protocols

Question

An $\mathcal{MA}$ communication complexity protocol is communication complexity protocol that starts with an omniscient prover that sends a proof (that depends on the the specific input of the players, but not on their random bits) to both players. The players then communicate with each other, in order to verify the proof (for more details, see: On Arthur Merlin Games in Communication Complexity, by Hartmut Klauck).

The are quite a few lower bounds (e.g., On the power of quantum proof, by Ran Raz and Amir Shplika) of the following form: Suppose we have a communication complexity problem $\mathcal{P}$ with a tight bound of $\Theta(T(n))$ on its communication complexity (for some function $T$). There exists a lower bound that shows that every $\mathcal{MA}$ communication complexity protocol that communicates $c$ bits and uses a proof of size $p$, must satisfy $c \cdot p = \Omega(T(n))$. So one can think of it as a tradeoff between the work that prover has to do, and the work that the verifiers have to do.

Moreover, it seems that for every communication complexity problem that I know of (with a tight bound of $\Theta(T(n))$ on its communication complexity), there exists a protocol wherein the prover sends a proof of size $\tilde O(T(n))$, and the verifiers only uses $\tilde O(1)$ bits of communication (cf. the two papers I mentioned above). Thus, in a sense, all of the work has been delegated to the prover (achieving the extreme case of the aforementioned lower bounds).

Is there a result that shows that a verifier-"heavy" protocol implies the existence of a prover-"heavy" protocol? Is there a counter example? What about other models (such as $\mathcal{MA}$ decision trees/query complexity) wherein our understanding of the behaviour of $\mathcal{MA}$ protocols is deeper?

Answer 1

This is an answer to the last question: MA in the query complexity model.

It isn't always possible to make the prover do all the work (or even any work at all). The reason is that an MA-prover is trying to convince you that the answer is YES. But the problem can be chosen so that in the YES case, there's nothing interesting that the prover can tell you. There are hard problems for which having a YES-prover is completely useless (i.e., it will not reduce the verifier's work at all).

For example, consider the AND problem, where you have to compute the AND of all the bits in the black box. This requires $\Omega(n)$ queries for a bounded-error algorithm. Now if you have access to a YES-prover, there's nothing interesting he can tell you. The most he could do is give you the entire contents of the black box. But since it is the AND function, and he is trying to convince you that the function evaluates to 1, he will always give you the all ones string. So you could have simulated this yourself.

Added: Does this protocol work in communication complexity? Take any CC problem that requires $T(n)$ bits of communication without Merlin. In the MA protocol, Merlin sends the entire transcript of communication to Alice and Bob, had they used the original protocol. Since equality is easy to check in randomized CC, they check that the transcripts are the same with high probability. Once they are convinced that the transcripts are the same, they output the outcome of that transcript of conversation.

Answer 2

It will depend on the model of communication: (1) If the proof is known by both players, (2) if only parts of it is known by Alice and the rest by Bob, or (3) if only one of the players receives the proof (say Alice). Plus, if the communication uses public or private coins.

For instance, in (3) with public coins, Merlin could send a copy of y to Alice, and check its correctness via a SMP-protocol or fingerprinting protocol. Then you can always communicate with Bob with $O(1)$ bits to tell him the correct answer. Also, considering the protocol in Robin Kothari's answer, Merlin could send the whole conversation in the proof, and then Alice and Bob just need to check if their parts are correct.

For more information on model (3) you can check Hartmut Klauck's paper. There you will also find a MA-protocol that meets your requirements, i.e., a "verifier-heavy" protocol. For model (2) you have Francois Le Gall's paper where he studies quantum/classical gaps. For (1) I have no reference to give you.