An Improved Line-Point Low-Degree Test

In this talk, I'll show that the most natural low-degree test for polynomials over finite fields is ``robust'' in the high-error regime for linear-sized fields. 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. The previous results in this space either worked only in the "low-error" regime (Polishchuk & Spielman, STOC 1994), or required q=Ω(d4)

(Arora & Sudan, Combinatorica 2003), or needed to measure local distance on 2-dimensional ``planes'' rather than one-dimensional lines leading to Ω(d2)

-query complexity (Raz & Safra, STOC 1997).

Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection (namely Hensel lifting) between multivariate factorization and finding (or testing) low-degree polynomials, in a non ``black-box'' manner in the context of root-finding.

Joint work with Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan.