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 >>>

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 >>>

{\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 >>>