arXiv preprint ·
On the Kissing Number of Craig's Lattice and Spherical List Decoding
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Craig's lattices $A_{p-1}^k$ are a family of lattices with large kissing numbers, i.e., relative to their dimension $n = p-1$, they contain a large number of shortest nonzero vectors. Specifically, for small $k = o(\log p / \log \log p)$, a lower bound of Bacher (2015) shows that $A_{p-1}^k$ has a super-polynomial kissing number of $ω(n^k)$. Craig's lattices are therefore attractive candidates for the construction of spherical codes. In this work, we introduce a polynomial-time list decoder for spherical codes obtained from Craig's lattices for angular distance below $45^\circ$. Our second main result shows that Bacher's lower bound is asymptotically tight for $k = o(\log p / \log \log p)$. Finally, we introduce an efficient algorithm for computing the kissing number of $A_{p-1}^k$. Using this algorithm, we compute their kissing number in dimensions up to 521. Based on this data, we pose the open question whether the kissing number of $A_{p-1}^k$ with $k \approx \sqrt{p}$ grows like $e^{Θ(\sqrt{n})}$ in dimension $n=p-1$. Concurrent work by Laarhoven and Kominers as well as Bennett, Hhan, Li and Stephens-Davidowitz proves such a bound for very closely related lattices.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Computed Permutation Trellis Coding: Near-Optimal Quantization from Two Multiplications and a 64-Byte Table
Fixed-Point Results and Disequilibrium for Negators of Hyperbolic-Valued Probability Distributions
Semantic Communication via Analog RF Computing: When the Radio Computes the Meaning
Subsystem Stabilizer $(r,δ)$-Locally Recoverable Codes: Characterization, Bounds and Constructions
Noise Characterization and Robust Signal Detection in Yeast Pheromone Molecular Communication
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.