STOC Conference 2025 Conference Paper
High Rate Multivariate Polynomial Evaluation Codes
- Swastik Kopparty
- Mrinal Kumar 0001
- Harry Sha
The classical Reed-Muller codes over a finite field F q are based on evaluations of m -variate polynomials of degree at most d over a product set U m , for some d 0. In fact, we give two quite different constructions, and for both we develop efficient decoding algorithms for these codes that can decode from half the minimum distance. The first of these codes is based on evaluating multivariate polynomials on simplex-like sets. The distance of this code is proved via a generalized Schwartz-Zippel lemma on the probability of non-zeroness when evaluating polynomials on sparser subsets of U m – the final bound only depends on the “shape” of the set, and recovers the Schwartz-Zippel bound for the case of the full U m , while still being Ω(1) for much sparser simplex-like subsets of U m . The second of these codes is more algebraic and, surprisingly (to us), has some strong locality properties. It is based on evaluating multivariate polynomials at the intersection points of hyperplanes in general position. It turns out that these evaluation points have many large subsets of collinear points. These subsets form the basis of a simple local characterization, and using some deeper algebraic tools generalizing ideas from Polischuk-Spielman, Raz-Safra, and Ben-Sasson-Sudan, we show that this gives a local test for these codes. Interestingly, the set of evaluation points for these locally testable multivariate polynomial evaluation codes can be as small as O ( d m ), and need not occupy a constant or even noticeable fraction of the full space F q m .