Robust Testing of Low-Degree and Lifted Codes

A local tester for a code probabilistically looks at a given word at a small set of coordinates and based on this local view accepts codewords with probability one while rejecting words far from the code with constant probability. A local tester for a code is said to be “robust” if the local views of the tester are far from acceptable views when the word being tested is far from the code. Robust testability of codes play a fundamental role in constructions of probabilistically checkable proofs where robustness is a critical element in composition.

In this talk we consider a broad class of codes, called lifted codes, that include codes formed by low-degree polynomials, and show that an almost natural test, extending a low-degree test proposed by Raz and Safra (STOC 1997), is robust. Our result is clean and general — the robustness of the test depends only on the distance of the code being lifted, and is positive whenever the distance is positive.

Based on joint work with Alan Guo and Madhu Sudan