2002 | Erik Agrell, Thomas Eriksson, Alexander Vardy, and Kenneth Zeger
This document, published in the IEEE Transactions on Information Theory, presents a comprehensive survey of closest-point search methods for lattices without regular structure. The authors describe existing search strategies in a unified framework and highlight their differences. They implement an efficient closest-point search algorithm based on the Schinor-Zechner variation of the Pohst method, which is shown to be significantly faster than other known methods through theoretical and experimental comparisons. The algorithm is designed to find the closest point in a lattice to a given vector $\mathbf{x} \in \mathbb{R}^m$ given a generator matrix $\mathbf{G}$. The paper also discusses modifications of the algorithm to solve related lattice search problems, such as finding the shortest vector, determining the kissing number, computing Voronoi-relevant vectors, and finding a Korkine-Zolotareff reduced basis. The authors provide a detailed pseudo-code implementation of the algorithm and discuss preprocessing techniques to improve its efficiency. The complexity analysis of the CLOSESTPOINT algorithm is presented, showing that it is faster than the Kannan algorithm for all dimensions and lattices. The paper concludes with a discussion on other lattice search problems and their solutions.This document, published in the IEEE Transactions on Information Theory, presents a comprehensive survey of closest-point search methods for lattices without regular structure. The authors describe existing search strategies in a unified framework and highlight their differences. They implement an efficient closest-point search algorithm based on the Schinor-Zechner variation of the Pohst method, which is shown to be significantly faster than other known methods through theoretical and experimental comparisons. The algorithm is designed to find the closest point in a lattice to a given vector $\mathbf{x} \in \mathbb{R}^m$ given a generator matrix $\mathbf{G}$. The paper also discusses modifications of the algorithm to solve related lattice search problems, such as finding the shortest vector, determining the kissing number, computing Voronoi-relevant vectors, and finding a Korkine-Zolotareff reduced basis. The authors provide a detailed pseudo-code implementation of the algorithm and discuss preprocessing techniques to improve its efficiency. The complexity analysis of the CLOSESTPOINT algorithm is presented, showing that it is faster than the Kannan algorithm for all dimensions and lattices. The paper concludes with a discussion on other lattice search problems and their solutions.