Videos

An Improved Line-Point Low-Degree Test

Presenter
September 23, 2024
Abstract
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.