Theory of Computing
-------------------
Title : From Local to Robust Testing via Agreement Testing
Authors : Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi
Volume : 18
Number : 12
Pages : 1-25
URL : https://theoryofcomputing.org/articles/v018a012
Abstract
--------
A local tester for an error-correcting code is a probabilistic
procedure that queries a small (sublinear) subset of coordinates,
accepts codewords with probability one, and rejects non-codewords with
probability proportional to their distance from the code. The local
tester is said to be _robust_ if for non-codewords it satisfies the
stronger condition that the average distance of local views from
accepting views is proportional to the distance from the code. Robust
testing is an important component in constructions of locally testable
codes and probabilistically checkable proofs as it allows for
composition of local tests.
We show that for certain codes, any (natural) local tester can be
converted to a robust tester with roughly the same number of queries.
Our result holds for the class of _affine-invariant lifted codes_
which is a broad class of codes that includes Reed--Muller codes, as
well as recent constructions of high-rate locally testable codes (Guo,
Kopparty, and Sudan, ITCS 2013). Instantiating this with known local
testing results for lifted codes gives a more direct proof that
improves some of the parameters of the main result of Guo, Haramaty,
and Sudan (FOCS 2015), showing robust soundness of lifted codes.
To obtain the above transformation, we relate the notions of local
testing and robust testing to the notion of _agreement testing_ that
attempts to find out whether valid partial assignments can be stitched
together to a global codeword. We first show that agreement testing
implies robust testing, and then show that local testing implies
agreement testing. Our proof is combinatorial, and is based on
sampling properties of the collection of local views of local testers.
Thus, it immediately applies to local testers of lifted codes that
query random affine subspaces in $\F_q^m$, and moreover seems amenable
to extension to other families of locally testable codes with
expanding families of local views.
-------------
A conference version of this paper appeared in the
Proceedings of the 10th Innovations in Theoretical
Computer Science Conference, 2019.