In this work, we show that the class of multivariate degree-d polynomials mapping \{0,1\}^{n} to any Abelian group G is locally correctable with \widetilde{O}_{d}((\log n)^{d}) queries for up to a fraction of errors approaching half the minimum distance of the underlying code. In particular, this result holds even for polynomials ... more >>>

We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain \{0,1\}^n over arbitrary fields and more generally Abelian groups. Such functions form error-correcting codes of relative distance 1/2 and we give local-correction algorithms correcting up to nearly 1/4-fraction errors making \widetilde{\mathcal{O}}(\log n) queries. This ... more >>>