Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
The unique shortest vector problem on a rational lattice is the problem of finding the shortest non-zero vector under the promise that it is unique (up to multiplication by -1). We give several incremental improvements on the known hardness of the unique shortest vector problem (uSVP) using standard techniques. This includes a deterministic reduction from the shortest vector problem to the uSVP, the NP-hardness of uSVP on (1 + 1/poly(n))-unique lattices, and a proof that the decision version of uSVP defined by Cai [4] is in co-NP for n(1/4)-unique lattices. (C) 2016 Published by Elsevier B.V.
Negar Kiyavash, Sina Akbari, Seyed Jalal Etesami