List Decoding, Linear Hashing, and Furstenberg over 𝔽q
Abstract
We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field 𝔽q. 1. Random linear codes over 𝔽q with rate 1 − Hq(p) − ε are (p, O(q Hq(p)/ε))-list decodable with high probability for all values of $p, q, ε$, including the high error regime. This nearly matches the list size lower bound of Hq(p)/ε due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for q > 2 since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over 𝔽q hashing n balls to n bins achieve maximum load O(q ln ln q / ln q) · ln n / ln ln n, both in expectation and with probability 1−o(1). This nearly matches the lower bound of ln n / ln ln n. Previously, only a polylogarithmic upper bound was known for q > 2, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set S by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside S than outside.
Related
- List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
- Spatially Coupled MacKay-Neal/Hsu-Anastasopoulos CSS Codes Achieve the Quantum-Erasure Hashing Bound by Seeded BP Decoding
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
- A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
BibTeX
@misc{kumar2026list,
title = {{List Decoding, Linear Hashing, and Furstenberg over $\mathbbF_q$}},
author = {Vinayak M. Kumar and Geoffrey Mon},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17020},
eprint = {2609.17020},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17020},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - List Decoding, Linear Hashing, and Furstenberg over 𝔽_q
AU - Vinayak M. Kumar
AU - Geoffrey Mon
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17020
UR - https://arxiv.org/abs/2609.17020
AB - We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field 𝔽_q. 1. Random linear codes over 𝔽_q with rate 1 − H_q(p) − ε are (p, O(q H_q(p)/ε))-list decodable with high probability for all values of $p, q, ε$, including the high error regime. This nearly matches the list size lower bound of H_q(p)/ε due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for q > 2 since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over 𝔽_q hashing n balls to n bins achieve maximum load O(q ln ln q / ln q) · ln n / ln ln n, both in expectation and with probability 1−o(1). This nearly matches the lower bound of ln n / ln ln n. Previously, only a polylogarithmic upper bound was known for q > 2, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set S by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside S than outside.
ER -