Cube-Root Soundness Is Optimal for the Line–versus–Point TestResearch Paper
The Reed–Muller code consists of the evaluation tables of polynomials of total degree at most . Restricted to an affine line, such a polynomial becomes a univariate polynomial of degree at most . The line–versus–point test checks exactly this local property. It is a two-query consistency test: given a…