High Rate Multivariate Polynomial Evaluation Codes

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 < |U|. Because of their good distance properties, as well as the ubiquity and expressive power of polynomials, these codes have played an influential role in coding theory and complexity theory. This is especially so in the setting of U being F q where they possess deep locality properties. However, these Reed-Muller codes have a significant limitation in terms of the rate achievable -the rate cannot be more than 1 m! = exp(-m log m). In this work, we give the first constructions of multivariate polynomial evaluation codes which overcome the rate limitation -concretely, we give explicit evaluation domains S ⊆ F m q on which evaluating m-variate polynomials of degree at most d gives a good code. For m = O(1), these new codes have relative distance Ω(1) and rate 1ε for any ε > 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 [PS94], Raz-Safra [RS97] and Ben-Sasson-Sudan [BSS06], 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 m q .