Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-043 | 2nd April 2015 15:56

Robust testing of lifted codes with applications to low-degree testing


Authors: Alan Guo, Elad Haramaty, Madhu Sudan
Publication: 2nd April 2015 15:57
Downloads: 818


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 probabilility. 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 work 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.

We use our result to get the first robust low-degree test that works when the degree of the polynomial being tested is more than half the field size. Our results also show that the high-rate codes of Guo et al.\ (ITCS 2013) are robustly locally testable with sublinear query complexity. Guo et al. also show several other interesting classes of locally testable codes that can be derived from lifting and our result shows all such codes have robust testers, at the cost of a quadratic blowup in the query complexity of the tester. Of technical interest is an intriguing relationship between tensor product codes and lifted codes that we explore and exploit.

ISSN 1433-8092 | Imprint