Approximate CVP in time 2^0.802 n – now in any norm!
share
We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time 2^0.802 n. This contrasts the corresponding 2^n time, (gap)-SETH based lower bounds for these problems that even apply for small constant approximation. For both problems, SVP and CVP, we reduce to the case of the Euclidean norm. A key technical ingredient in that reduction is a twist of Milman's construction of an M-ellipsoid which approximates any symmetric convex body K with an ellipsoid ℰ so that 2^ε n translates of a constant scaling of ℰ can cover K and vice versa.
READ FULL TEXT