An Improved Line-Point Low-Degree Test

We prove that the most natural low-degree test for polynomials over finite fields is robust'' in the high-error regime for linear-sized fields. Specifically we consider the local’’ agreement of a function $f:{\mathbb{F}}_q^m\to {\mathbb{F}}_q$ from the space of degree-$d$ polynomials, i.e., the expected agreement of the function from univariate degree-$d$ polynomials over a randomly chosen line in ${\mathbb{F}}_q^m$, and prove that if this local agreement is $\epsilon \ge \mathrm{\Omega }((\frac{d}{q}{)}^{\tau }))$ for some fixed $\tau >0$, then there is a global degree-$d$ polynomial $Q:{\mathbb{F}}_q^m\to {\mathbb{F}}_q$ with agreement nearly $\epsilon$ with $f$. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$-query robust test in the high-error'' regime (i.e., when $ε< \frac{1}{2}$). The previous results in this space either required $ε> \frac{1}{2}$ (Polishchuk \& Spielman, STOC 1994), or $q = Ω(d^4)$ (Arora \& Sudan, Combinatorica 2003), or needed to measure local distance on $2$-dimensional planes’’ rather than one-dimensional lines leading to $\mathrm{\Omega }(d^2)$-query complexity (Raz & Safra, STOC 1997). Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case ($m=O(1)$) and then bootstrapping'' to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non black-box’’ manner. A second contribution is a bootstrapping analysis which manages to lift analyses for $m=2$ directly to analyses for general $m$, where previous works needed to work with $m=3$ or $m=4$ – arguably this bootstrapping is significantly simpler than those in prior works.