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