Locally Testable Cyclic Codes

Cyclic linear codes of block length n over a finite field F/sub q/ are the linear subspaces of F/sub q//sup n/ that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes based on F. J. MacWilliams and N. J. A. Sloane (1977). A code C is r-testable if there exist a randomized algorithm which, given a word x /spl isin/ F/sub q//sup n/, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that (i) if x /spl isin/ C then x is surely accepted; (ii) if dist(x, C) /spl ges/ /spl epsi/n then x is probably rejected (dist refers to Hamming distance). A family of codes is locally testable if all members of the family are r-testable for some constant r. This concept arose from holographic proofs/PCPs. O. Goldreich and M. Sudan (2002) asked whether there exist good, locally testable families of codes. In this paper we address the intersection of the two questions stated.

Authors

• László Babai
• Amir Shpilka
• Daniel Stefankovic

Keywords

• Testing
• Computer science
• Cyclic Codes
• Decision-making
• Holographic
• Block Length
• Finite Field
• Linear Code
• Root Of Unity
• Family Of Codes
• Binary Code
• Divisible
• Information Bits
• Codeword
• Divisor
• Parity-check
• Number Theory
• Linear Length
• Alphabet Size
• Principal Domains
• Principal Ideal
• Strong Trade-off