Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ARTHUR-MERLIN PROTOCOLS:
Reports tagged with Arthur-Merlin protocols:
TR09-146 | 29th December 2009
Dan Gutfreund, Akinori Kawachi

Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if $\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$ then there is a Boolean function in $\mathrm{E}^{\mathrm{NP}}$ that requires ... more >>>


TR15-206 | 15th December 2015
Benny Applebaum, Pavel Raykov

From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

Goos, Pitassi and Watson (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur-Merlin Protocols (ZAM). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs $x$ and $y$ respectively, and Merlin, the ... more >>>


TR18-088 | 24th April 2018
Ilya Volkovich

A story of AM and Unique-SAT

Revisions: 1

In the seminal work of \cite{Babai85}, Babai have introduced \emph{Arthur-Merlin Protocols} and in particular the complexity classes $MA$ and $AM$ as randomized extensions of the class $NP$. While it is easy to see that $NP \subseteq MA \subseteq AM$, it has been a long standing open question whether these classes ... more >>>


TR23-029 | 18th March 2023
Nicollas Sdroievski, Dieter van Melkebeek

Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols

A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the ... more >>>




ISSN 1433-8092 | Imprint