An Improved Line-Point Low-Degree Test - Prahladh Harsha

Computer Science/Discrete Mathematics Seminar I
11:00am|Simonyi 101 and Remote Access
Topic: An Improved Line-Point Low-Degree Test
Speaker: Prahladh Harsha
Affiliation: Tata Institute of Fundamental Research
Date: September 23, 2024

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.