Tag Info

New answers tagged


The equations mod 1 are supposed to have solutions that are very close to an integer value, say 3.99 or 4.01, which are reduced to a value very close to 0 (or 1, which is 0 mod 1). Specifically, they describe a set of samples that equate to the distance from an integer value all within $± {1/n}$ for some large value $n$, and the sum of the sample set is ...


I am not aware of any work that proposes a Gap problem related to LWE. The reason is probably that LWE is an average-case problem specifically designed for the use in crypto. However, there are the related worst-case problems, e.g. the shortest vector problem (SVP), that come with a Gap version. So, you might want to have a look at GapSVP and GapCVP.

Top 50 recent answers are included