Computer Science/Discrete Mathematics Seminar I

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= \Omega(d^4)$ (Arora & Sudan, Combinatorica 2003), or needed to measure local distance on 2-dimensional ``planes'' rather than one-dimensional lines leading to $\Omega(d^2)$-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.