An improved line-point low-degree test*

Abstract

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:F^m_q→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 F^m_q, and prove that if this local agreement is ε≥Ω((d/q)^τ)) for some fixed τ>0, then there is a global degree-d polynomial Q:^m_q→F_q with agreement nearly ε 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 ε<1/2). The previous results in this space either required ε>1/2 (Polishchuk & Spielman, STOC 1994), or q=Ω(d⁴) (Arora & Sudan, Combinatorica 2003), orneeded to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to Ω(d²) -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 “boot-strapping” 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. This connection was used roughly in a black-box manner in the work of Arora & Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. 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.