Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOW-DEGREE TEST:
Reports tagged with low-degree test:
TR23-182 | 21st November 2023
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

An Improved Line-Point Low-Degree Test

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 ``local'' agreement of a function $f\colon \mathbb{F}_q^m \to \mathbb{F}_q$ from the space of degree-$d$ polynomials, i.e., the expected agreement of the function from univariate ... more >>>




ISSN 1433-8092 | Imprint