The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that $n$-variate non-zero polynomial functions of degree $d$ over a field $\mathbb{F}$, are non-zero over any ``grid'' (points of the form $S^n$ for finite subset $S \subseteq \mathbb{F}$) with probability at least $\max\{|S|^{-d/(|S|-1)},1-d/|S|\}$ over the choice of random point from the grid. In particular, ... more >>>

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 >>>