#GoldreichTestableCodesSurvey-5
"Local testability
By local testability we mean that the object can be tested for the natural property (i.e., being a codeword or a valid proof) using a small (typically constant)[Footnote: In this part, we associate local testability with tests
>
"Local testability
By local testability we mean that the object can be tested for the natural property (i.e., being a codeword or a valid proof) using a small (typically constant)[Footnote: In this part, we associate local testability with tests
>
>that perform a constant number of probes.] number of probes, each recovering individual bits in a standard representation of the object. Thus, local testability allows for super-fast testing of the corresponding objects. The tests are probabilistic and hence the result
>
>
>is correct only with high probability.[Footnote: It is easy to see that deterministic tests will perform very poorly, and the same holds with respect to probabilistic tests that make no error.] Furthermore, correctness refers to a relaxed notion of deciding (which
>
>
>was formulated, in general terms, in the context of property testing [SIAM Journal on Computing 25(2), 252–271 (1996)], [Journal of the ACM 45(4), 653–750 (1998)]): It is required that valid objects be accepted with high probability, whereas objects that are “far” from being
>
>
>valid should be rejected with high probability. Specifically, in the case of #codes, codewords should be accepted (with high probability), whereas strings that are “far” from the code should be rejected (with high probability). In the case of proofs, valid proofs
>
>
• • •
Missing some Tweet in this thread? You can try to
force a refresh
