Oded Goldreich

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

VyasRam Selvam

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

Oded Goldreich, Avi Wigderson

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