An Improved Line-Point Low-Degree Test

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi +1

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 ``loc…