Oded's choices (Nr. 41)

Some recent results on testing of sparse linear codes

by Swastik Kopparty and Shubhangi Saraf.

Oded's comments

Shubhangi advocated viewing locally testable linear codes as a special case of tolerant testing the Hadamard codewords under some adequate distributions (specifically, the distribution that is uniform on the corresponding positions of the Hadamard code). The tolerance condition prevents rejecting a codeword based on positions that are assigned zero probability. She presented two results, relating to two notion of tolerant testing (or rather distance approximaton): the more general result yields a weak notion of approximation and may obtained under the so-called uniformly correlated condition, whereas a strong notion of approximation requires a stronger correlated condition. A distribution $\mu$ is called $k$-uniformly correlated if there is a joint distribution of $k$-tuples such that each element (in the $k$-tuple) is distributed as $\mu$ but their sum is uniformly distributed. The stronger condition requires that this holds when there $k$ elements are independently drawn from $\mu$, which is equivalent to requiring that the code be sparse and have small Fourier coefficients.

The original abstract

We study the problem of tolerant linearity testing under general distributions, as well as an important special case, the problem of locally testing linear codes.

Given a distribution $μ$ over $F_2^n$ and a function $f: F_2^n \to F_2$, we are interested in distinguishing (using very few queries to f), between (1) the case where $f$ is $μ$ -close to a linear function, and (2) the case where $f$ is $μ$ -far from all linear functions (here $μ$ -distance between functions f, g is measured by the probability that f and g differ on a random point sampled from $μ$ ). For every linear code $C$, there is a distribution $μ$ for which tolerant linearity testing implies the local testability of $C$.

Via this connection, we give a very simple proof that sparse random linear codes are locally testable (and locally list-decodable) from $(1 / 2 - ε)$ -fraction errors with constantly many queries, for every constant $ε > 0$ . More precisely, we show that any linear code in $F_2^n$ that is:

sparse (i.e., has only poly(n) codewords)
unbiased (i.e., each nonzero codeword has Hamming weight in $(1/2-n^{-\gamma}, 1/2 + n^{-\gamma})$ for some constant $γ > 0$ )

can be locally tested and locally list decoded from $(1 / 2 - ε)$ -fraction errors using only $poly(1/\epsilon)$ queries to the received word. This simultaneously simplifies and strengthens a result of Kaufman and Sudan, who gave a local tester and local (unique) decoder for such codes from some constant fraction of errors.

We also give a general criterion which implies that linearity is testable under a given distribution. This condition, for example, implies that linearity is testable under the p-biased distribution.

Back to list of Oded's choices.