Metraipolis › archive › dc_4e8b8a278182

List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$ — arXiv:2609.17020

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.17020
License (as archived)
CC0-1.0
Archived
2026-10-15T21:59:15.734Z
SHA-256 of the archived text
08b5629012950338d7a8427d85a16197a13eebc65a9011c7ec1195676e057dc6
Stable URL of this page
https://metraipolis.com/documento/dc_4e8b8a278182

How to cite

List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$ — arXiv:2609.17020 — arXiv (en), https://arxiv.org/abs/2609.17020 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4e8b8a278182 (Metraipolis archive dc_4e8b8a278182, sha256 08b5629012950338d7a8427d85a16197a13eebc65a9011c7ec1195676e057dc6)
BibTeX
@misc{dc4e8b8a278182,
  title = {List Decoding, Linear Hashing, and Furstenberg over $mathbbF_q$ — arXiv:2609.17020},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.17020},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4e8b8a278182; sha256 08b5629012950338d7a8427d85a16197a13eebc65a9011c7ec1195676e057dc6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.17020. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for all values of $p, q, \epsilon$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/\epsilon$ 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 $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in cs.DS).
Categorie arXiv: Information Theory (cs.IT) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO); Number Theory (math.NT).
Pagina del lavoro: https://arxiv.org/abs/2609.17020 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T21:46:54.594Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).