An Improved Nearest Plane Algorithm for Closest Vector Problem

TL;DRAbstract

The Closest Vector Problem (CVP) is the most intensively studied problem in the algorithmic geometry of numbers. It has been shown by Van and Emde Boas that CVP is NP-hard. There is no known algorithm to approximate CVP within a polynomial factor of the dimension of the lattice. Recently, Koy proposed primal-dual reduction which has better quality than LLL-reduction in high-dimensional lattice. In this paper, an improved algorithm named PNP using Koy's primal-dual reduction is proposed to approximate CVP, which extend from the nearest plane algorithm on LLL bases developed by Babai. The output of PNP algorithm, compared with Babai's, has better approximate factor and PNP algorithm can finish its computing in nearly polynomial time.

Chat with Paper

AI Agents for this Paper