CS Paper Radar

On the Kissing Number of Craig's Lattice and Spherical List Decoding

Léo Ducas, Julian Nowakowski, Ailsa Robertson

cs.IT ·submitted 2026-11-17 09:12 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

A Note on Sphere Packing Bounds for Tuple Lattice Sieving

cs.CR math.COcs.ITmath.MG ·2026-09-08 ·Thijs Laarhoven
similarity 0.69
Abstract · 6 pages, 1 figure

A finite set of unit vectors is $k$-irreducible if every signed sum of between two and $k$ distinct elements has norm greater than one. Let $\mathcal{R}_k$ be the maximal asymptotic rate of such sets, and let $κ(α)$ be the maximal asymptotic rate of spherical codes with pairwise inner products at most $α$. For $k \ge 2$ we show: \begin{align} \mathcal{R}_k \le \min_{1 \le r \le \lfloor k/2 \rfloor} \frac{1}{r} \, κ\!\left(1 - \frac{1}{2r}\right) \, . \end{align} Combining this with standard sphere packing bounds, for large $k$ we obtain an almost-tight asymptotic comparison with the known lower bounds: \begin{align} \left(\tfrac{1}{2}-o(1)\right) \, \frac{\log_2 k}{k} \le \mathcal{R}_k \le (1 + o(1)) \, \frac{\log_2 k}{k} \, . \end{align}

0.24

List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding

cs.IT ·2026-09-01 ·Chen Yuan, Ruiqi Zhu
theory similarity 0.68
Abstract · 32 pages

Guruswami, Li, Mosheiff, Resch, Silas and Wootters conjectured that, for every fixed prime power $q$ and $p\in(0,1-1/q)$, random linear codes of rate $1-h_q(p)-\varepsilon$ have list size $\frac{h_q(p)}{\varepsilon}\cdot(1+o(1))$ as $\varepsilon\to0$, both for list decoding and average-radius list decoding. The conjecture was known for $q=2$ and remained open for larger alphabets. We prove the conjecture for list decoding for every prime power $q$, with the sharper bound $L=\frac{h_q(p)}{\varepsilon}+O_{p,q}(1).$ In contrast, we disprove the conjecture for average-radius list decoding. We show that the required list-size leading constant is at least $p\left(1+\log_q\frac{(q-1)(1-p)}{p}\right)$, which is strictly larger than $h_q(p)$ whenever $q^p(1-p)>1$. Moreover, for $p=1-λ/q$ with fixed $λ>1$, the required leading constant can be as large as $\left(\frac{\logλ}{eλ}+o_q(1)\right)\frac{q}{\log q}.$

0.44

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.65
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families

cs.CC cs.DMcs.IT ·2026-08-28 ·Sidhant Saraogi
publishedtheory similarity 0.65
Abstract · 11 pages

Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial method argument that controls collisions in sumsets of matching vectors.

0.27

Asymptotic Bounds for Codes in Toroidal Distance

cs.IT ·2026-11-19 ·Pengjie Zhong, Jinquan Luo
theory similarity 0.63
Abstract

The toroidal distance naturally describes the geometry of codes over \(\mathbb Z_q\), where distances are measured modulo \(q\). In this paper, we study asymptotic bounds for codes in \(\mathbb Z_q^n\) under the toroidal metric. We first derive an explicit asymptotic lower bound from the classical Gilbert--Varshamov bounds for the Hamming and Lee metrics, which serves as a baseline for comparison. We then develop a saddle-point approach for the toroidal metric, which yields an asymptotic Gilbert--Varshamov lower bound and an asymptotic Hamming-type upper bound. For \(3\mid q\), we embed ternary Hamming codes into \(\mathbb Z_q^n\) and obtain another asymptotic lower bound for the toroidal metric. In addition, we derive an asymptotic lower bound for Maximum Toroidal Distance (MTD) codes. We compare these lower bounds with the baseline and prove that they are nontrivial in the corresponding parameter ranges. Finally, we compare the asymptotic bounds numerically.

0.15

The half-rate linear programming bound for binary codes is $\frac12-\frac1π$

cs.IT math.CO ·2026-09-03 ·Andrew Salmon
theory similarity 0.63
Abstract · 33 pages

In their work on sphere packing and the modular bootstrap, Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini conjectured the exact high-dimensional exponent of the Cohn-Elkies sphere-packing linear program. OpenAI's Chapter 1 subsequently proved their conjecture by establishing that both Fourier sign-uncertainty radii are $(1/π+o(1))\sqrt d$. We prove the binary coding analogue: \[ R_D\!\left(\frac12-\frac1π\right)=\frac12. \] We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If $A^{\mathrm K}_{\pm}(n)$ denotes the smallest radius $r$ for which a nonzero Krawtchouk $(\pm1)$-eigenfunction $f$ exists with $f(0) = 0$ and $f(x) \ge 0$ for all $|x| \ge r$, then \[ \frac{A^{\mathrm K}_{\pm}(n)}n\longrightarrow \frac12-\frac1π. \] The lower bound proves a mass-concentration principle similar to OpenAI's Chapter 1 for Hamming space. The upper bound, on the other hand, follows the approach of the spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu formulated a hierarchy for binary codes analogous to the spherical-code construction and improved the best known binary coding rate bounds by evaluating the first level of the corresponding hierarchy. We prove this hierarchy bounds the Delsarte program and give a construction at arbitrarily deep levels of the hierarchy, attaining the upper bound in the limit. The construction uses an $N$-qubit generalization of the pure-state channel of Alrabiah and Guruswami.

0.52

Deterministic Constructions of Reed-Solomon Codes Beyond the Johnson Bound

cs.CC ·2026-10-22 ·Abhranil Chatterjee, Sumanta Ghosh, Zeyu Guo, Rohit Gurjar, Roshan Raj +1 more
similarity 0.63
Abstract

We give a deterministic quasipolynomial-time construction of Reed-Solomon codes that are list-decodable beyond the Johnson radius. Specifically, for every $ε\in(0,1]$ and all sufficiently large $n$, we construct an $[n,k]$ Reed-Solomon code of rate $R=Ω(ε/(1+\log(1/ε)))$ over a field of size $(nk)^{quasi-poly(nk)}$ that is $(1-ε,O(1/ε))$ list-decodable. The construction runs in quasi-poly(nk) time. We also give a deterministic construction of $[n,k]$-MDS$(3)$ Reed-Solomon codes for all integers $1\leq k<n$, with the same asymptotic bounds on field size and construction time. In the constant-rate regime, our field-size bound substantially improves the bound of $O(n^{k^{2k}})$ achieved by Roth's construction (Roth, IEEE TIT 2022). Our constructions exploit a connection to polynomial identity testing for read-once determinants, together with the quasipolynomial isolating-weight construction of Gurjar and Thierauf for linear matroid intersection (Gurjar and Thierauf, STOC 2017 and Computational Complexity 2020).

0.20

Combinatorial limitations of list-decoding Reed-Solomon codes

cs.IT cs.CC ·2026-11-05 ·Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami
similarity 0.62
Abstract · 24 pages

For infinitely many rates $R \in (0,1)$, we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just exceeding the Johnson radius. Over prime fields, we exhibit full-length Reed-Solomon codes of constant rate $R$ with polynomially many codewords in a Hamming ball of relative radius bounded strictly below $1-R$. This refutes a recent conjecture that, over prime fields, list sizes below capacity are always bounded by a constant. Together, these results demonstrate that certain restrictions in recent works on explicit Reed-Solomon codes achieving list-decoding capacity, related to the choice of field or evaluation points or to the list-size guarantee, are inherent.

0.36