Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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