{"id":"arxiv/2609.17020","url":"https://arxiv.org/abs/2609.17020","tags":["cs.IT","cs.CC","cs.DS","math.CO","math.NT"],"score":0,"title":"List Decoding, Linear Hashing, and Furstenberg over $\\mathbb{F}_q$","domain":"cs.IT","source":"arxiv","authors":["Vinayak M. Kumar","Geoffrey Mon"],"reviews":0,"subject":"cs.IT","summary":"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) - ε$ 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}