A lattice L in R^n is a discrete subgroup of R^n.
Let p IN [1,infinty)
The p-norm of a vector x=(x_1,...,x_n) IN R^n is
||x||_p=(|x_1|^p + ... + |x_n|^p)^{1/p}.
Note that p=2 yields the standard Euclidean distance.
If p=infinity then ||x||_p=max_{1 LE i LE n} |x_i|.
Let p IN [1,infinity]
The Shortest Vector Problem in norm p (SVP_p) is as follows:
INPUT A lattice L specified by a basis.
OUTPUT Output the shortest vector in that basis using the p-norm.
I was looking at lower bounds on approximating this problem and just assumed the original problem was NP-hard. Much to my surprise either (a) its not known, or (b) it is known and I missed in in my lit search. I am hoping that comments on this post will either verify (a) or tell me (b) with refs.
Here is what I found:
Peter van Emde Boas in 1979 showed that SVP_infinity is NP-hard.
(See here for a page that has a link to the paper. I was unable to post the link directly. Its where it says I found the original paper.) He conjectured that for all p GE 1 the problem is NP-hard.
Miklos Ajtai in 1998 showed that SVP_2 is NP-hard under randomized reductions. (See here)
There are other results by Subhash Khot in 2005 (see here) and Divesh Aggarwal et al. in 2021 (see here) (Also see the references in those two papers.) about lower bounds on approximation using a variety of assumptions. Aggarwal's paper in unusual in that it shows hardness results for all p except p even; however, this is likely a function of the proof techniques and not of reality. Likely these problems are hard for all p.
But even after all of those great papers it seems that the the statement:
For all p IN [1,infinity] SVP_p is NP-hard
is a conjecture, not a theorem. I wonder if van Emde Boas would be surprised. If he reads this blog, maybe I'll find out. If you know him then ask him to comment, or comment yourself.
SO is that still a conjecture OR have I missed something?
(Oddly enough, my own blog post here (item 5) indicates SVP_p is NP-hard; however,
I have not been able to track down the reference.)
You're right that SVP_2 (arguably the most interesting case) is not known to be NP hard under determinstic reductions unconditionally. Some useful references for the problem are the papers by Daniele Micciancio
ReplyDelete*Inapproximability of the Shortest Vector Problem: Toward a
Deterministic Reduction*, and *Locally Dense Codes*.
Essentially, NP hardness of SVP_2 reduces to constructing a certain geometric object. There are known probabilistic constructions, and a deterministic construction (conditional on a certain number-theoretic conjecture).
I have heard that recent constructions of dense efficiently-decodable lattices (due to Peikert and some other authors) may be good candidates for locally dense lattices (which by Micciancio's work would solve the problem), but haven't looked into the problem myself.
As the above anonymous reader writes, indeed the deterministic hardness of SVP for any norm other than l_infinity, remains an open problem to this day. Proving the number theoretic conjecture stated by Micciancio that would imply a deterministic reduction, seems to be out of reach with current techniques.
ReplyDeleteThe latest paper by Bennett and Peikert contains all references and discusses potential obstacles of a coding theory approach to prove NP-Hardness. I cannot verify this right now, but IIRC all approaches we have, do have a coding theory flavor essentially.
https://arxiv. org/abs/2202.07736
Indeed, SVP in any l_p norm with p < infinity, including in the important Euclidean case of p = 2, is not known to be NP-hard under deterministic Karp reductions. Trying to remedy this is a notorious open question.
ReplyDeleteThe most recent work on this problem is my joint paper with Chris Peikert: https://arxiv.org/abs/2202.07736. It uses Reed-Solomon codes to give a relatively simple randomized hardness reduction to SVP and gives concrete directions for derandomizing it.
For anyone interested, I will be giving a talk both about our new work and about the problem in general this Thursday: https://simons.berkeley.edu/talks/hardness-shortest-vector-problem-new-proof-and-retrospective.
Peter's last name is "van Emde Boas" not "Boas"
ReplyDeletethanks fixed.
Delete