Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
The problem of deciding whether a given rational lattice L has a vector of length less than some given value r is addressed. It is demonstrated that this problem is NP-hard under randomized reductions, even under the promise that L has exactly zero or one vector of length less than r.
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Ronald Fagin, Ravi Kumar, et al.
SIAM Journal on Discrete Mathematics
Ronald Fagin, Ravi Kumar, et al.
SIAM Journal on Discrete Mathematics
Miklos Ajtai, R. Kumar, et al.
STOC 2001