Approximate CVP in Time 2(0.802n) - Now in Any Norm!
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 E so that 2(epsilon n) translates of a constant scaling of E can cover K and vice versa.
WOS:000870458800031
2022-01-01
Cham
978-3-031-06901-7
978-3-031-06900-0
Lecture Notes in Computer Science
13265
440
453
REVIEWED
Event name | Event place | Event date |
Eindhoven, NETHERLANDS | Jun 27-29, 2022 | |