Error-correcting codes and related combinatorial constructs play an important role in several recent (and old) results in computational complexity theory. In this paper we survey results on locally-testable and locally-decodable error-correcting codes, and their applications to complexity theory and to cryptography. Locally decodable codes are error-correcting codes with sub-linear time ... more >>>

We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically ... more >>>

We give constructions of PCPs of length n*polylog(n) (with respect to circuits of size n) that can be verified by making polylog(n) queries to bits of the proof. These PCPs are not only shorter than previous ones, but also simpler. Our (only) building blocks are Reed-Solomon codes and the bivariate ... more >>>

We survey known results regarding locally testable codes and locally testable proofs (known as PCPs), with emphasis on the length of these constructs. Locally testability refers to approximately testing large objects based on a very small number of probes, each retrieving a single bit in the representation of the object. ... more >>>

An error-correcting code is said to be {\em locally testable} if it has an efficient spot-checking procedure that can distinguish codewords from strings that are far from every codeword, looking at very few locations of the input in doing so. Locally testable codes (LTCs) have generated a lot of interest ... more >>>

Let C={c_1,...,c_n} be a set of constraints over a set of variables. The {\em satisfiability-gap} of C is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the variables. We prove a new combinatorial amplification lemma that doubles the satisfiability-gap of a constraint-system, with only a linear ... more >>>

Given a function f:F^m \rightarrow F over a finite field F, a low degree tester tests its proximity to an m-variate polynomial of total degree at most d over F. The tester is usually given access to an oracle A providing the supposed restrictions of f to affine subspaces of ... more >>>

Ben-Sasson and Sudan in~\cite{BS04} asked if the following test is robust for the tensor product of a code with another code-- pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that for ... more >>>

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>>

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... more >>>

Motivated by questions in property testing, we search for linear error-correcting codes that have the ``single local orbit'' property: i.e., they are specified by a single local constraint and its translations under the symmetry group of the code. We show that the dual of every ``sparse'' binary code whose coordinates ... more >>>

The Unique Games Conjecture (UGC) is possibly the most important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC ... more >>>

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is ... more >>>

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable (in particular sparse random codes are locally testable). Kopparty ... more >>>