Loading...
research article
Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward
A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψlog(nψ)) , where ψ=sqrt(P ||h||^2+1) depends on the transmission power and the norm of the channel vector. We will then extend our results to integer-forcing and finally introduce a more general class of lattices for which the SVP and the closest vector problem can be approximated within a constant factor.
Type
research article
Web of Science ID
WOS:000416211900019
Authors
Publication date
2017
Published in
Volume
63
Issue
12
Start page
7780
End page
7792
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
November 23, 2017
Use this identifier to reference this record