Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPUTATIONAL PROBLEMS IN INTEGER LATTICES:
Reports tagged with Computational Problems in Integer Lattices:
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 >>>

TR99-002 | 22nd January 1999
Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

#### Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.

$f$, the following holds: