From: David A Molnar <dmolnar@fas.harvard.edu>
Subject: Re: lattices, NPI
Date: 2 May 2000 11:19:01 GMT
Newsgroups: sci.math
Summary: [missing]

Approximating the closest vector problem or the shortest vector problem
for sufficiently large approximation factors has been the thing
recently. A factor of O(2^n) (n dimension of lattice) can be done by LLL
in polytime. The exact problems are NP-hard. In the middle, no one
knows...although it has been shown by Goldreich and Goldwasser[1] that
if it's NP-hard to approximate either within sqrt(n) or more, then the
polytime hierarchy collapses, so maybe that's someplace to look. 

Thanks,
-David

[1] "On The Limits of the Non-Approximability of Lattice Problems"
but I can't remember the rest of the reference.

John Carpenter <carpente@cs.unc.edu> wrote:
> Does anyone know of any problems perhaps relating to lattice reductions
> whose computational complexity is suspected to be NP-Incomplete (i.e.
> not in P, in NP, but not NP-hard --other examples include graph
> isomorphism and factorization )?

> Thanks,
> John Carpenter
> carpente@cs.unc.edu
==============================================================================

From: David A Molnar <dmolnar@fas.harvard.edu>
Subject: Re: lattices, NPI
Date: 2 May 2000 14:04:49 GMT
Newsgroups: sci.math

David A Molnar <dmolnar@fas.harvard.edu> wrote:

> [1] "On The Limits of the Non-Approximability of Lattice Problems"
> but I can't remember the rest of the reference.

Ok, I have a little time to do this correctly now :

Oded Goldreich, Shafi Goldwasser: On the Limits of Non-Approximability
of Lattice Problems. STOC 1998: 1-9
ftp://theory.lcs.mit.edu/pub/people/oded/lp.ps

See also these two survey papers for more on the closest vector and
shortest vector problems (and their slight variants) and some experience
with their difficulty in practice : 

Jin-Yi Cai 
Some Recent Progress on the Complexity of Lattice Problems 
ECCC Report TR99-006, accepted on Mar 11, 1999.
(I'm sure it's been published somewhere else by now, but this is
one of the easier ways to get it)
ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1999/TR99-006/index.html


Phong Nguyen and Jacques Stern 
Lattice Reduction in Cryptography : An Update
Algorithmic Number Theory -- Proceedings of ANTS-IV 
http://www.di.ens.fr/~pnguyen/pub.html#NgSt00


There very well may be other NPI problems associated with lattices
(counting the number of lattice points within a convex polytope, maybe?)
but these are the ones which have attracted most recent interest. I
would like to know of other problems in this area which "look hard"...

Thanks, 
-David Molnar