ECCC-Report TR17-031https://eccc.weizmann.ac.il/report/2017/031Comments and Revisions published for TR17-031en-usMon, 20 Apr 2020 23:07:50 +0300
Revision 1
| Quadratic Simulations of Merlin-Arthur Games |
Thomas Watson
https://eccc.weizmann.ac.il/report/2017/031#revision1The 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).
Mon, 20 Apr 2020 23:07:50 +0300https://eccc.weizmann.ac.il/report/2017/031#revision1
Paper TR17-031
| Quadratic Simulations of Merlin-Arthur Games |
Thomas Watson
https://eccc.weizmann.ac.il/report/2017/031The 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).
Sun, 19 Feb 2017 09:28:19 +0200https://eccc.weizmann.ac.il/report/2017/031