Title: On the Communication Cost of Determining an Approximate Nearest Lattice Point,
Abstract: We consider the closest lattice point problem in a distributed network
setting and study the communication cost and the error probability for
computing an approximate nearest lattice point, using the nearest-plane
algorithm, due to Babai. Two distinct communication models, centralized and
interactive, are considered. The importance of proper basis selection is
addressed. Assuming a reduced basis for a two-dimensional lattice, we determine
the approximation error of the nearest plane algorithm. The communication cost
for determining the Babai point, or equivalently, for constructing the
rectangular nearest-plane partition, is calculated in the interactive setting.
For the centralized model, an algorithm is presented for reducing the
communication cost of the nearest plane algorithm in an arbitrary number of
dimensions.