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