Local Testability and Decodability of Sparse Linear Codes

Long time no post...

Madhu Sudan gave an interesting talk at Tsinghua University.

paper (Kaufman, Sudan)

Some of my notes.

fixed error correcting code, oracle access, check whether correct word resp. not too corrupt, local correction if close to a word, local testing and local correction

example: Hadamard code

code C
linear: x,y \in C => x+y \in C
sparse: t-sparse if C <= n^t (only polynomially many codewords, quite restrictive) large distance: \gamma large distance if for all code words distance at least 1/2-n^-\gamma, as close to 1/2 as possible if these conditions, then k-locally testable (if in addition balanced, k-locally correctible) linear code: dual: all words orthogonal to all code words, dual code also linear => pick a word of dual code, check whether it is orthogonal, that's the check. word should be of low weight (weight k) to allow for a k-local test

corrector to correct coordinate i needs a low-weight word in the dual where coordinate i is 1 and the rest is roughly uniform

=> does dual code have low weight words? roughly uniform even with restriction coordinate i is 1?

weight distribution of primal code: C_i = number of codewords in C with weight i

actually want distribution of dual code C_k^\perp

from primal to dual code weight distributions: MacWilliams identities, hold if we know C_i EXACTLY
C_k^\perp = 1/C \sum C_i P_k(i)
where P_k(i) = \sum (-1)^j (i choose j) (n-i choose k-j) is Krawtchouk Polynomial

the codeword 0 (C_0={0}) contributes most to the sum, polynomial has high value there, low value at all other C_k, as not too many codewords it does not cancel out the highly weighted 0 word

doesn't work for unbalanced because low weight words in dual not guaranteed

and: don't know how to find these words...