Towards a Converse for the Nearest Lattice Point Problem

Abstract

Upper bounds on the communication complexity of finding the nearest lattice point in a given lattice $\Lambda \subset {\mathbb{R}}^2$ was considered in earlier works~\cite{VB:2017}, for a two party, interactive communication model. Here we derive a lower bound on the communication complexity of a key step in that procedure. Specifically, the problem considered is that of interactively finding $\min (X_1,X_2)$, when $(X_1,X_2)$ is uniformly distributed on the unit square. A lower bound is derived on the single-shot interactive communication complexity and shown to be tight. This is accomplished by characterizing the constraints placed on the partition generated by an interactive code and exploiting a self similarity property of an optimal solution.

6 pages, 4 figures. arXiv admin note: text overlap with arXiv:1701.08458

References in corpus (2)

• Distributed Scalar Quantization for Computing: High-Resolution Analysis and Extensions
• Communication Cost of Transforming a Nearest Plane Partition to the Voronoi Partition