Talk:Lattice problem

SVP example

In the Shortest Vector Problem illustration, I am not sure that the black vectors generate the lattice represented by the dots. Cédric VAN ROMPAY (talk) 15:16, 22 January 2015 (UTC) Cédric VAN ROMPAY

Completely unintelligible to a non-expert

As someone with a basic knowledge linear algebra, I should be able to read this article and understand the gist of what the problem is. But only someone that is already an expert in the field could understand this. The use of very terse notations that depend on definitions that depend on other definitions in subtle ways, combined with the lack of useful examples is the issue.

I had a similar issue with the RSA article, which described the algorithim in terms of Eulers Totient function. I added an easily understood explanation in terms of Fermats Little theorum, which people tried to remove (have not looked recently).

The goal is not to show how clever you are. Nor to preach only to fellow experts (that is what the academic literature is for). The goal is to make it intelligible to non-experts int he field. But without dumbing it down into mush.Tuntable (talk) 02:27, 20 June 2018 (UTC)

Notation for SVP, ${\text{SVP}}_{\gamma }$, etc...

I don't think that we should have SVP that is not enclosed in a math environment, then immediately have ${\text{SVP}}_{\gamma }$ which is in a math environment. I can't search inside the math brackets in Chrome, and it also looks ugly. I'll keep the subscripts in math, but remove the text. Sanpitch (talk) 05:44, 28 March 2019 (UTC)

Citation 4 claims to prove that SVPgamma under the infinity norm assuming gamma is an integer is NP-complete

Says it all in the title. Note the original publication can be found here and that publication uses different names than in the wikipedia article.

The problem the author refers to as the "closest vector" problem is to find a non-zero lattice vector whose infinity norm is bounded by some positive integer K, which is exactly SVPgamma with gamma = K.

Someone ought to check the equivalence between the problems and review the proof and alter the "hardness result" subsection if I am correct. If I am not correct, then that paper demonstrates a lattice problem that has been proven to be NP-complete. — Preceding unsigned comment added by Bggoode (talk • contribs) 19:12, 1 September 2020 (UTC)