Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AM:
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