Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Approximate CVPp in time 2(0.802n)
 
research article

Approximate CVPp in time 2(0.802n)

Eisenbrand, Friedrich  
•
Venzin, Moritz  
March 1, 2022
Journal Of Computer And System Sciences

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.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.jcss.2021.09.006
Web of Science ID

WOS:000711661500002

Author(s)
Eisenbrand, Friedrich  
Venzin, Moritz  
Date Issued

2022-03-01

Publisher

ACADEMIC PRESS INC ELSEVIER SCIENCE

Published in
Journal Of Computer And System Sciences
Volume

124

Start page

129

End page

139

Subjects

Computer Science, Hardware & Architecture

•

Computer Science, Theory & Methods

•

Computer Science

•

lattice and integer programming

•

algorithmic geometry of numbers

•

sieving

•

geometric covering

•

shortest vector problem

•

lattice vectors

•

algorithm

•

hardness

•

points

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Available on Infoscience
January 31, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/184867
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés