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 games:
TR96-018 | 23rd February 1996
Oded Goldreich, Johan Hastad

On the Message Complexity of Interactive Proof Systems

Revisions: 2

We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized a probabilitic machine
in time ... more >>>

TR97-054 | 17th November 1997
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

Arthur-Merlin Games in Boolean Decision Trees

It is well known that probabilistic boolean decision trees
cannot be much more powerful than deterministic ones (N.~Nisan, SIAM
Journal on Computing, 20(6):999--1007, 1991). Motivated by a question
if randomization can significantly speed up a nondeterministic
computation via a boolean decision tree, we address structural
properties of Arthur-Merlin games ... more >>>

TR98-075 | 9th December 1998
Adam Klivans, Dieter van Melkebeek

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

We establish hardness versus randomness trade-offs for a
broad class of randomized procedures. In particular, we create efficient
nondeterministic simulations of bounded round Arthur-Merlin games using
a language in exponential time that cannot be decided by polynomial
size oracle circuits with access to satisfiability. We show that every
language with ... more >>>

TR01-046 | 2nd July 2001
Oded Goldreich, Salil Vadhan, Avi Wigderson

On Interactive Proofs with a Laconic Prover

We continue the investigation of interactive proofs with bounded
communication, as initiated by Goldreich and Hastad (IPL 1998).
Let $L$ be a language that has an interactive proof in which the prover
sends few (say $b$) bits to the verifier.
We prove that the complement $\bar L$ has ... more >>>

TR04-007 | 13th January 2004
Alan L. Selman, Samik Sengupta

Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy

Revisions: 1 , Comments: 1

It is known \cite{BHZ87} that if every language in coNP has a
constant-round interactive proof system, then the polynomial hierarchy
collapses. On the other hand, Lund {\em et al}.\ \cite{LFKN92} have shown that
#SAT, the #P-complete function that outputs the number of satisfying
assignments of a Boolean ... more >>>

TR04-086 | 12th October 2004
Ronen Shaltiel, Chris Umans

Pseudorandomness for Approximate Counting and Sampling

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.

Our main technical contribution allows one to ``boost'' a given hardness assumption. One special ... more >>>

TR07-069 | 29th July 2007
Ronen Shaltiel, Chris Umans

Low-end uniform hardness vs. randomness tradeoffs for AM

In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP in the {\em uniform setting}, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan (in a slightly weaker setting). In 2003, Gutfreund, Shaltiel and Ta-Shma proved ... more >>>

TR10-019 | 19th February 2010
Andrew Drucker

A PCP Characterization of AM

We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class $\mathsf{AM}$. This gives a `PCP characterization' of $\mathsf{AM}$ analogous to the PCP Theorem for $\mathsf{NP}$. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, ... more >>>

TR10-174 | 12th November 2010
Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games

We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit ... more >>>

TR12-080 | 18th June 2012
Baris Aydinlioglu, Dieter van Melkebeek

Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games

In several settings derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in *any* way implies ... more >>>

TR12-091 | 16th July 2012
Abuzer Yakaryilmaz

One-counter verifiers for decidable languages

Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working ... more >>>

TR12-130 | 3rd October 2012
Abuzer Yakaryilmaz

Public-qubits versus private-coins

We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on space-bounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems ... more >>>

ISSN 1433-8092 | Imprint