Rothvoss, ThomasVenzin, Moritz2022-11-072022-11-072022-11-072022-01-0110.1007/978-3-031-06901-7_33https://infoscience.epfl.ch/handle/20.500.14299/191925WOS:000870458800031We 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 E so that 2(epsilon n) translates of a constant scaling of E can cover K and vice versa.Computer Science, Theory & MethodsMathematics, AppliedComputer ScienceMathematicslattice algorithmssievinginteger programmingshortest vector problemlattice problemshardnessreductionlimitstext::conference output::conference proceedings::conference paper