Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LATTICE, UNIQUE SHORTEST VECTOR, DECISION VS SEARCH, NP-HARDNESS, HARDNESS OF APPROXIMATION:
Reports tagged with Lattice, Unique Shortest Vector, Decision vs Search, NP-hardness, Hardness of Approximation:
TR13-076 | 15th May 2013
Divesh Aggarwal, Chandan Dubey

Improved hardness results for unique shortest vector problem

Revisions: 1

We give several improvements on the known hardness of the unique shortest vector problem in lattices, i.e., the problem of finding a shortest vector in a given lattice given a promise that the shortest vector is unique upto a uniqueness factor $\gamma$.
We give a deterministic reduction from the ... more >>>




ISSN 1433-8092 | Imprint