On Communication for Distributed Babai Point Computation

Authors

Maiara F. Bollauf, Simula UiBFollow
Vinay A. Vaishampayan, CUNY College of Staten IslandFollow
Sueli I.R. Costa, University of CampinasFollow

Document Type

Article

Publication Date

7-16-2021

Abstract

We present a communication-efficient distributed protocol for computing the Babai point, an approximate nearest point for a random vector X∈Rn in a given lattice. We show that the protocol is optimal in the sense that it minimizes the sum rate when the components of X are mutually independent. We then investigate the error probability, i.e. the probability that the Babai point does not coincide with the nearest lattice point, motivated by the fact that for some cases, a distributed algorithm for finding the Babai point is sufficient for finding the nearest lattice point itself. Two different probability models for X are considered—uniform and Gaussian. For the uniform model, in dimensions two and three, the error probability is seen to grow with the packing density, and we demonstrate that the densest lattice in dimension two presents the worst error probability. For higher dimensions, we develop probabilistic concentration bounds as well as bounds based on geometric arguments for the error probability. The probabilistic bounds lead to the conclusion that for lattices which generate suitably thin coverings of Rn (which includes lattices that meet Rogers’ bound on the covering radius), the error probability goes to unity as n grows. Probabilistic and geometric bounds are also used to estimate the error probability under the uniform model for various lattices including the An family and the Leech lattice, Λ24 . On the other hand, for the Gaussian model, the error probability goes to zero as the lattice dimension tends to infinity, provided the noise variance is sufficiently small.

Comments

This work was originally published in IEEE Transactions on Information Theory, available at DOI 10.1109/TIT.2021.3097719