๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the Limits of Nonapproximability of Lattice Problems

โœ Scribed by Oded Goldreich; Shafi Goldwasser

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
221 KB
Volume
60
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor ofn, 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 ofn is in NP & coAM. Thus, it seems unlikely that approximating these problems to within an factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al.

๐Ÿ“œ SIMILAR VOLUMES

On the Problem of Stability in Lattice D
On the Problem of Stability in Lattice Dynamical Systems
โœ L.A. Bunimovich; E.A. Carlen ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 513 KB

We present methods for establishing the full non-linear stabilty of solutions of lattice dynamical systems. We apply these results to establish the existence of a "chaos-order" phase transition in a particular coupled map lattice model for which space time chaos in the small coupling regime had been