Sahraei, SaeidGastpar, Michael C.2017-11-232017-11-232017-11-23201710.1109/TIT.2017.2759281https://infoscience.epfl.ch/handle/20.500.14299/142292WOS:000416211900019A 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.LatticesComplexity theoryApproximation algorithmsRelaysDecodingMatrix decompositionLinear matrix inequalitiesShortest vector problemclosest vector problemcompute-and-forwardinteger-forcingtext::journal::journal article::research article