Abstract

Error correcting codes are combinatorial objects that allow reliable recovery of information in presence of errors by cleverly augmenting the original information with a certain amount of redundancy.
The availability of efficient means of error detection is considered as a fundamental criterion for error correcting codes. Locally testable codes are families of error correcting codes that are highly robust against transmission errors and in addition provide super-efficient (sublinear time) probabilistic algorithms for error detection. In particular, the error detection algorithm probes the received sequence only at a small (or even constant) number of locations.
There seems to be a trade-off between the amount of redundancy and the number of probes for the error detection procedure in locally testable codes. Even though currently best constructions allow reduction of redundancy to a nearly linear amount, it is not clear whether this can be further reduced to linear while preserving a constant number of probes.
We study the formal notion of locally testable codes and survey several major results in this area. We also investigate closely related concepts, and in particular, polynomial low-degree tests and probabilistically checkable proofs.

Keywords:
Error Correcting Codes, Locally Testable Codes, Probabilistically Checkable Proofs (PCP), Low-Degree Tests, Hardness of Approximation.

Table of Contents

Abstract . . . . . . . . . . . . . . . . . . . . . . v
Acknowledgements . . . . . . . . . . . . . . . . . . vi

1 Introduction . . . . . . . . . . . . . . . . . . . 1

2 Preliminaries and Notation . . . . . . . . . . . . 6
2.1 Error correcting codes . . . . . . . . . . . . . 6
2.2 The tradeoff between rate and distance . . . . . 9
2.3 Linear codes . . . . . . . . . . . . . . . . . . 11
2.4 Composition of the codes . . . . . . . . . . . . 13
2.4.1 Concatenated codes . . . . . . . . . . . . . . 14
2.4.2 Tensor product . . . . . . . . . . . . . . . . 14
2.4.3 Tanner product . . . . . . . . . . . . . . . . 15
2.5 Reed-Solomon codes and related constructions . . 16
2.6 Oracle machines  . . . . . . . . . . . . . . . . 19

3 A Toolbox of Polynomials . . . . . . . . . . . . . 21
3.1 Basic notions and facts  . . . . . . . . . . . . 21
3.2 Low-degree tests . . . . . . . . . . . . . . . . 25
3.2.1 Linearity test . . . . . . . . . . . . . . . . 26
3.2.2 Univariate low-degree test . . . . . . . . . . 27
3.2.3 Multivariate low-degree test . . . . . . . . . 29

4 Efficient Verification of Codewords 32
4.1 Definition . . . . . . . . . . . . . . . . . . . 32
4.2 Constructions  . . . . . . . . . . . . . . . . . 37
4.2.1 Testing Reed-Muller codes  . . . . . . . . . . 37
4.2.2 Polynomial-Line codes  . . . . . . . . . . . . 38
4.2.3 Tensor product codes . . . . . . . . . . . . . 42

5 Codeword Test by Proof Checking  . . . . . . . . . 45
5.1 Probabilistically Checkable Proofs . . . . . . . 47
5.1.1 Definitions and facts  . . . . . . . . . . . . 47
5.1.2 Relationship with locally testable codes . . . 49
5.2 Hardness of approximation and efficient PCPs . . 50
5.3 PCPs of proximity  . . . . . . . . . . . . . . . 54
5.3.1 Formal definition  . . . . . . . . . . . . . . 55
5.3.2 Robustness and composition . . . . . . . . . . 56
5.3.3 Nearly linear-sized PCPPs  . . . . . . . . . . 58
5.3.4 PCPPs and locally testable codes . . . . . . . 61
5.4 Combinatorial constructions  . . . . . . . . . . 62

6 Conclusions and Related Work . . . . . . . . . . . 67
Bibliography . . . . . . . . . . . . . . . . . . . . 72