Loading...
research article
Approximate CVPp in time 2(0.802n)
March 1, 2022
We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vector problem in the l(2) norm. To obtain our result, we combine the latter algorithm for l(2) with geometric insights related to coverings. (C) 2021 Published by Elsevier Inc.
Use this identifier to reference this record
Type
research article
Web of Science ID
WOS:000711661500002
Authors
Publication date
2022-03-01
Publisher
Published in
Volume
124
Start page
129
End page
139
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
January 31, 2022