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.
Type
research article
Web of Science ID
WOS:000711661500002
Author(s)
Date Issued
2022-03-01
Publisher
Published in
Volume
124
Start page
129
End page
139
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
January 31, 2022
Use this identifier to reference this record