Computer Science/Discrete Mathematics Seminar I

A code is said to be locally testable if an algorithm can distinguish between a codeword and a vector being essentially far from the code using a number of queries that is independent of the code's length. The question of characterizing codes that are locally testable is highly complex. In this work we provide a sufficient condition for linear codes `to be locally testable. Our condition is based on the weight distribution (spectrum) of the code and of its dual. Codes of length $n$ and minimum distance $n/2-\Theta(\sqrt{n})$ have size which is at most polynomial in $n$. We call such codes almost orthogonal. We use our condition to show that almost orthogonal codes are locally testable, and, moreover, their dual codes can be spanned by words of constant weights (weight of a codeword refers to the number of its non-zero coordinates). Dual-BCH codes are generalizations of the well studied Hadamard codes, and are known to be almost orthogonal. Alon et al. raised the question whether these codes are locally testable. Our result provides positive answer to this question. Moreover, it shows that the BCH codes are spanned by their almost shortest words. Joint work with Simon Litsyn