2018/01/29 by Maiara F. Bollauf, Bollauf, Maiara F., Vinay A. Vaishampayan +3
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Digital Image Processing Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Interconnection Networks and Systems #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1801.09796
arxiv created 2018/01/29 · openalex publication_date 2018/01/29 · arxiv updated 2018/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of finding the closest lattice point to a vector in n-dimensional Euclidean space when each component of the vector is available at a distinct node in a network. Our objectives are (i) minimize the communication cost and (ii) obtain the error probability. The approximate closest lattice point considered here is the one obtained using the nearest-plane (Babai) algorithm. Assuming a triangular special basis for the lattice, we develop communication-efficient protocols for computing the approximate lattice point and determine the communication cost for lattices of dimension n>1. Based on available parameterizations of reduced bases, we determine the error probability of the nearest plane algorithm for two dimensional lattices analytically, and present a computational error estimation algorithm in three dimensions. For dimensions 2 and 3, our results show that the error probability increases with the packing density of the lattice.