Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with AM:
TR97-031 | 9th September 1997
Oded Goldreich

On the Limits of Non-Approximability of Lattice Problems

Revisions: 2

We show simple constant-round interactive proof systems for
problems capturing the approximability, to within a factor of $\sqrt{n}$,
of optimization problems in integer lattices; specifically,
the closest vector problem (CVP), and the shortest vector problem (SVP).
These interactive proofs are for the ``coNP direction'';
that is, ... 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 >>>

TR13-152 | 7th November 2013
Oded Goldreich, Avi Wigderson

On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

{\em Does derandomization of probabilistic algorithms become easier when the number of ``bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ... more >>>

ISSN 1433-8092 | Imprint