Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-060 | 27th April 2022 19:50

How much randomness is needed to convert MA protocols to AM protocols?


Authors: Nikolay Vereshchagin
Publication: 27th April 2022 19:52
Downloads: 279


The Merlin-Arthur class of languages MA is included into Arthur-Merlin class AM, and into PP. For a standard transformation of a given MA protocol with Arthur's message (= random string) of length $a$ and Merlin's message of length $m$ to a PP machine, the latter needs $O(ma)$ random bits. The same holds for simulating MA protocols by AM protocols: in the resulting AM protocol the length of Arthur's message (= random string) is $O(ma)$. And the same holds for simulating heuristic MA protocols by heuristic AM protocols as well. In the paper [A. Knop, Circuit Lower Bounds for Average-Case MA, CSR 2015] it was conjectured that, in the transformation of heuristic MA protocols to heuristic AM protocols, $O(ma)$ can be replaced by a polynomial of $a$ only. A similar question can be asked for normal MA and AM protocols, and for the simulation of MA protocols by PP machines. In the present paper we show that, relative to an oracle, both latter questions answer in the negative and Knop's conjecture is false. Moreover, the same is true for simulation of MA protocols by AM protocols in which the error probability is not bounded away from 1/2, the so called PP$\cdot$NP protocols. The latter protocols generalize both AM protocols and PP machines.

ISSN 1433-8092 | Imprint