Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ARTHUR-MERLIN:
Reports tagged with Arthur-Merlin:
TR09-109 | 3rd November 2009
Kai-Min Chung, Feng-Hao Liu

#### Tight Parallel Repetition Theorems for Public-coin Arguments

Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results:

1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is, $n$-fold parallel repetition ... more >>>

TR13-144 | 8th October 2013
VyasRam Selvam

#### The two queries assumption and Arthur-Merlin classes

We explore the implications of the two queries assumption, $P^{NP[1]}=P_{||}^{NP[2]}$, with respect to the polynomial hierarchy and the classes $AM$ and $MA$.
We prove the following results:

1. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $AM = MA$
2. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH \subset MA_{/1}$
3. $\exists\;B\;P^{NP[1]^B}=P^{NP[2]^B}$ and $NP^B \not\subseteq coMA^B$.
4. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH ... more >>> TR14-012 | 27th January 2014 Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz #### AM with Multiple Merlins Revisions: 1 We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close ... more >>> TR18-019 | 28th January 2018 Zeyu Guo, Nitin Saxena, Amit Sinhababu #### Algebraic dependencies and PSPACE algorithms in approximative complexity Revisions: 1 Testing whether a set$\mathbf{f}$of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}\$ (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). ... more >>>

ISSN 1433-8092 | Imprint