Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-031 | 20th April 2020 23:07

Quadratic Simulations of Merlin-Arthur Games

RSS-Feed




Revision #1
Authors: Thomas Watson
Accepted on: 20th April 2020 23:07
Downloads: 328
Keywords: 


Abstract:

The known proofs of $\text{MA}\subseteq\text{PP}$ incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which $\text{MA-TIME}(t)\not\subseteq\text{P-TIME}(o(t^2))$. We also show that 2-sided-error Merlin--Arthur games can be simulated by 1-sided-error Arthur--Merlin games with quadratic overhead. We also present a simple, query complexity based proof (provided by Mika G\"o\"os) that there is an oracle relative to which $\text{MA}\not\subseteq\text{NP}^{\text{BPP}}$ (which was previously known to hold by a proof using generics).


Paper:

TR17-031 | 15th February 2017 18:35

Quadratic Simulations of Merlin-Arthur Games





TR17-031
Authors: Thomas Watson
Publication: 19th February 2017 09:28
Downloads: 937
Keywords: 


Abstract:

The known proofs of $\text{MA}\subseteq\text{PP}$ incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which $\text{MA-TIME}(t)\not\subseteq\text{P-TIME}(o(t^2))$. We also show that 2-sided-error Merlin--Arthur games can be simulated by 1-sided-error Arthur--Merlin games with quadratic overhead. We also present a simple, query complexity based proof (provided by Mika G\"o\"os) that there is an oracle relative to which $\text{MA}\not\subseteq\text{NP}^{\text{BPP}}$ (which was previously known to hold by a proof using generics).



ISSN 1433-8092 | Imprint