Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR18-198 | 25th December 2020 14:14

From Local to Robust Testing via Agreement Testing

RSS-Feed




Revision #2
Authors: Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi
Accepted on: 25th December 2020 14:14
Downloads: 473
Keywords: 


Abstract:

A local tester for an error-correcting code is a probabilistic procedure that queries a small 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 {\em robust} if for non-codewords it satisfies the stronger property 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.

In this work we show that for certain codes, any (natural) local tester can be converted to a roubst tester with roughly the same number of queries.
Our result holds for the class of {\em 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 robustness of lifted codes.

To obtain the above transformation we relate the notions of local testing and robust testing to the notion of {\em 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 expansion / 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.



Changes to previous version:

Revision per final journal version


Revision #1 to TR18-198 | 29th January 2019 16:01

From Local to Robust Testing via Agreement Testing





Revision #1
Authors: Irit Dinur, Tali Kaufman, Noga Ron-Zewi, Prahladh Harsha
Accepted on: 29th January 2019 16:01
Downloads: 794
Keywords: 


Abstract:

A local tester for an error-correcting code is a probabilistic procedure that queries a small 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 property 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.

In this work, 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 robustness 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 expansion / 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.



Changes to previous version:

Amended author list


Paper:

TR18-198 | 22nd November 2018 22:56

From Local to Robust Testing via Agreement Testing





TR18-198
Authors: Irit Dinur, Tali Kaufman, Noga Ron-Zewi
Publication: 23rd November 2018 09:30
Downloads: 1027
Keywords: 


Abstract:

A local tester for an error-correcting code is a probabilistic procedure that queries a small 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 {\em robust} if for non-codewords it satisfies the stronger property 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.

In this work we show that for certain codes, any (natural) local tester can be converted to a roubst tester with roughly the same number of queries.
Our result holds for the class of {\em 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 robustness of lifted codes.

To obtain the above transformation we relate the notions of local testing and robust testing to the notion of {\em 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 expansion / 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.



ISSN 1433-8092 | Imprint