ECCC-Report TR97-031https://eccc.weizmann.ac.il/report/1997/031Comments and Revisions published for TR97-031en-usSun, 22 Feb 1998 00:00:00 +0200
Revision 2
| On the Limits of Non-Approximability of Lattice Problems Revision of: TR97-031 |
Oded Goldreich
https://eccc.weizmann.ac.il/report/1997/031#revision2We 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, we give an interactive protocol
showing that a vector is ``far'' from the lattice (for CVP),
and an interactive protocol
showing that the shortest-lattice-vector is ``long'' (for SVP).
Furthermore, these interactive proof systems
are Honest-Verifier Perfect Zero-Knowledge.
We conclude that approximating CVP (resp., SVP) within a factor
of $\sqrt{n}$ is in $NP\cap coAM$.
Thus, it seems unlikely that approximating these problems
to within a $\sqrt{n}$ factor is NP-hard.
Previously, for the CVP (resp., SVP) problem,
Lagarias et al, Hastad and Banaszczyk showed
that the gap problem corresponding to
approximating CVP (resp., SVP) within $n$ is in $NP\cap\coNP$.
On the other hand, Arora et al showed that the gap problem corresponding
to approximating CVP within $2^{\log^{0.999}n}$ is quasi-NP-hard.
Sun, 22 Feb 1998 00:00:00 +0200https://eccc.weizmann.ac.il/report/1997/031#revision2
Revision 1
| On the Limits of Non-Approximability of Lattice Problems Revision of: TR97-031 |
Oded Goldreich
https://eccc.weizmann.ac.il/report/1997/031#revision1We 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, we give an interactive protocol
showing that a vector is ``far'' from the lattice (for CVP),
and an interactive protocol
showing that the shortest-lattice-vector is ``long'' (for SVP).
Furthermore, these interactive proof systems
are Honest-Verifier Perfect Zero-Knowledge.
We conclude that approximating CVP (resp., SVP) within a factor
of $\sqrt{n}$ is in $NP\cap coAM$.
Thus, it seems unlikely that approximating these problems
to within a $\sqrt{n}$ factor is NP-hard.
Previously, for the CVP (resp., SVP) problem,
Lagarias et al, Hastad and Banaszczyk showed
that the gap problem corresponding to
approximating CVP (resp., SVP) within $n$ is in $NP\cap\coNP$.
On the other hand, Arora et al showed that the gap problem corresponding
to approximating CVP within $2^{\log^{0.999}n}$ is quasi-NP-hard.
Thu, 16 Oct 1997 00:00:00 +0200https://eccc.weizmann.ac.il/report/1997/031#revision1
Paper TR97-031
| On the Limits of Non-Approximability of Lattice Problems |
Oded Goldreich
https://eccc.weizmann.ac.il/report/1997/031We 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, we give an interactive protocol
showing that a vector is ``far'' from the lattice (for CVP),
and an interactive protocol
showing that the shortest-lattice-vector is ``long'' (for SVP).
Furthermore, these interactive proof systems
are Honest-Verifier Perfect Zero-Knowledge.
We conclude that approximating CVP (resp., SVP) within a factor
of $\sqrt{n}$ is in $NP\cap coAM$.
Thus, it seems unlikely that approximating these problems
to within a $\sqrt{n}$ factor is NP-hard.
Previously, for the CVP (resp., SVP) problem, Lagarias et al showed
that the gap problem corresponding to approximating CVP within $n^{1.5}$
(resp., approximating SVP within $n$) is in $NP\cap coNP$.
On the other hand, Arora et al showed that the gap problem corresponding
to approximating CVP within $2^{\log^{0.499}n}$ is quasi-NP-hard.
Wed, 10 Sep 1997 09:22:57 +0300https://eccc.weizmann.ac.il/report/1997/031