New bounds improve error correction and hashing over finite fields
List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$
Information TheoryComputational ComplexityData Structures and Algorithms
Summary
The paper finds tighter limits for how well certain error-correcting codes can handle errors and how balanced certain hashing methods can be when working over mathematical objects called finite fields. The authors improve known results for when the number of possible symbols is greater than two, helping codes correct more errors with fewer guesses. They also show how to better organize items in bins using linear hashing so no bin gets overloaded. Their approach connects these practical problems to an abstract geometric concept called Furstenberg sets, using a new math technique involving polynomials.
What this means in practice
- •For software engineers: Design error-correcting codes that can handle more errors with fewer guesses in data communication systems over larger alphabets.
- •For database administrators: Build hashing schemes that evenly distribute data into buckets with minimal maximum load to optimize speed and storage.
Authors
Vinayak M. Kumar, Geoffrey Mon
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) - ε$ 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 $\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.