High Rate Multivariate Polynomial Evaluation Codes

The classical Reed-Muller codes over a finite field $\mathbb{F}_q$ are based on evaluations of $m$-variate polynomials of degree at most $d$ over a product set $U^m$, for some $d$ less than $|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 ${\mathbb{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 $\frac{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 \subseteq \mathbb{F}_q^m$ 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 $\Omega(1)$ and rate $1 - \epsilon$ for any $\epsilon > 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 whereas the second construction is more algebraic, and surprisingly (to us), has some strong locality properties, specifically, we show that they are locally testable.