List Decoding, Linear Hashing, and Furstenberg over ${\mathbb{F}}_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 ${\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.