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 ... 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 ... 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 ... 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 ... 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 >>>

Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For ``global properties'', i.e., properties that really depend somewhat on every piece of the data, one could ask ... more >>>

A linear code is said to be affine-invariant if the coordinates of the code can be viewed as a vector space and the code is invariant under an affine transformation of the coordinates. A code is said to be locally testable if proximity of a received word
to the code ... more >>>

A distance estimator is a code together with a randomized algorithm. The algorithm approximates the distance of any word from the code by making a small number of queries to the word. One such example is the Reed-Muller code equipped with an appropriate algorithm. It has polynomial length, polylogarithmic alphabet ... more >>>

This paper describes recent results which revolve around the question of the rate attainable by families of error correcting codes that are locally testable. Emphasis is placed on motivating the problem of proving upper bounds on the rate of these codes and a number of interesting open questions for future ... more >>>

We study the relation between locally testable and locally decodable codes.
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. Locally decodable codes (LDCs) allow to recover each message entry with ... more >>>

Inspired by recent construction of high-rate locally correctable codes with sublinear query complexity due to
Kopparty, Saraf and Yekhanin (2010) we address the similar question for locally testable codes (LTCs).

In this note we show a construction of high-rate LTCs with sublinear query complexity.
More formally, we show that for ... more >>>

Locally testable codes, i.e., codes where membership in the code is testable with a constant number of queries, have played a central role in complexity theory. It is well known that a code must be a "low-density parity check" (LDPC) code for it to be locally testable, but few LDPC ... more >>>

The main open problem in the area of locally testable codes (LTCs) is whether there exists an asymptotically good family of LTCs and to resolve this question it suffices to consider the case of query complexity $3$. We argue that to refute the existence of such an asymptotically good family ... more >>>

In this paper we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the First composition theorem showing that repeating the two-wise tensor operation any constant number of times still results in a locally testable code, improving upon previous ... more >>>

Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as ... more >>>

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field ${\mathbb{F}}_q$ and an extension field ${\mathbb{F}}_{q^n}$, a property is a set of functions mapping ${\mathbb{F}}_{q^n}$ to ${\mathbb{F}}_q$. The property is said to be affine-invariant if it ... more >>>

In this work we explore error-correcting codes derived from
the ``lifting'' of ``affine-invariant'' codes.
Affine-invariant codes are simply linear codes whose coordinates
are a vector space over a field and which are invariant under
affine-transformations of the coordinate space. Lifting takes codes
defined over a vector space of small dimension ... more >>>

In this work we explore error-correcting codes derived from
the ``lifting'' of ``affine-invariant'' codes.
Affine-invariant codes are simply linear codes whose coordinates
are a vector space over a field and which are invariant under
affine-transformations of the coordinate space. Lifting takes codes
defined over a vector space of small dimension ... more >>>

The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate-limit of LTCs ... more >>>

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a randomized algorithm (tester) that makes at most $q$ queries to the input word. This algorithm accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot ... more >>>

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of "affine-invariant'' codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes ... more >>>

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity
of property testing via communication complexity. They provided a restricted formulation of their methodology
(via ``simple combining operators'')
and also hinted towards a more general formulation, which we spell ... more >>>

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\begin{enumerate}
\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a ... more >>>

We develop new techniques to incorporate the recently proposed ``short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical ``Label Cover + Fourier Analysis'' framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs ... more >>>

Locally testable codes (LTCs) are error-correcting codes
that admit very efficient codeword tests. An LTC is said to
be strong if it has a proximity-oblivious tester;
that is, a tester that makes only a constant number of queries
and reject non-codewords with probability that depends solely
on their distance from ... more >>>

We initiate a study of learning and testing dynamic environments,
focusing on environment that evolve according to a fixed local rule.
The (proper) learning task consists of obtaining the initial configuration
of the environment, whereas for non-proper learning it suffices to predict
its future values. The testing task consists of ... more >>>

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

A local tester for a code probabilistically looks at a given word at a small set of coordinates and based on this local view accepts codewords with probability one while rejecting words far from the code with constant probabilility. A local tester for a code is said to be ``robust'' ... more >>>

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

An error correcting code is said to be \emph{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 small number of symbols
of the string. Locally testable codes (LTCs) are both interesting
in their ... more >>>

We initiate a study of ``universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \{ f_i : \{0,1\}^k \to \{0,1\} \}_{i ... more >>>

Motivated by the structural analogies between point lattices and linear error-correcting codes, and by the mature theory on locally testable codes, we initiate a systematic study of local testing for membership in lattices. Testing membership in lattices is also motivated in practice, by applications to integer programming, error detection in ... more >>>

Universal locally testable codes (Universal-LTCs), recently introduced in our companion paper [GG16], are codes that admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. In this work, we initiate the study of the NP analogue of these codes, wherein the testing procedures ... more >>>

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>

We survey the state of the art in constructions of locally testable
codes, locally decodable codes and locally correctable codes of high rate.

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.

We present general results about the local testability of linear codes in the non-signaling ... more >>>

We cement the intuitive connection between relaxed local correctability and local testing by presenting a concrete framework for building a relaxed locally correctable code from any family of linear locally testable codes with sufficiently high rate. When instantiated using the locally testable codes of Dinur et al. (STOC 2022), this ... more >>>