tag:blogger.com,1999:blog-3722233.post414280661681721253..comments2023-09-28T12:45:24.391-05:00Comments on Computational Complexity: I am surprised that the Shortest Vector Problem is not known to be NP-hard, but perhaps I am wrongLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-8465835671784984142022-06-16T14:05:41.455-05:002022-06-16T14:05:41.455-05:00thanks fixed.thanks fixed.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64412194425950356732022-06-16T12:05:47.349-05:002022-06-16T12:05:47.349-05:00Peter's last name is "van Emde Boas"...Peter's last name is "van Emde Boas" not "Boas"Ronald de Wolfhttp://homepages.cwi.nl/~rdewolf/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33692671620933725752022-06-13T15:31:40.088-05:002022-06-13T15:31:40.088-05:00Indeed, SVP in any l_p norm with p < infinity, ...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.<br /><br />The 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.<br /><br />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.Huck Bennetthttps://web.engr.oregonstate.edu/~bennethu/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64102798890677068452022-06-13T05:58:52.676-05:002022-06-13T05:58:52.676-05:00As the above anonymous reader writes, indeed the d...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.<br />The 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.<br /><br />https://arxiv. org/abs/2202.07736Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23384169796785345852022-06-12T15:03:10.610-05:002022-06-12T15:03:10.610-05:00You're right that SVP_2 (arguably the most int...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<br /><br />*Inapproximability of the Shortest Vector Problem: Toward a<br />Deterministic Reduction*, and *Locally Dense Codes*.<br /><br />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).<br /><br />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.Anonymousnoreply@blogger.com