2017/11/13 by Vinay A. Vaishampayan, Vaishampayan, Vinay A.
Computer Science · Engineering · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1711.04714
6 pages, 4 figures. arXiv admin note: text overlap with arXiv:1701.08458
openalex publication_date 2017/11/13 · arxiv created 2018/03/24 · arxiv updated 2018/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Upper bounds on the communication complexity of finding the nearest lattice point in a given lattice Λ⊂ ℝ2 was considered in earlier works~\citeVB: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(X1,X2), when (X1,X2) 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.