Name
Abstract | ||
|---|---|---|
Cyclic linear codes of block length n over a finite field \mathbb{F}_qare the linear subspace of \mathbb{F}_{_q }^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 (cf. [MS, p. 270]).A code C is r-testable if there exist a randomized algorithm which, given a word x \in \mathbb{F}_q^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 \in C then x is surely accepted;if dist(x,C) \geqslant \varepsilon n then x is probably rejected.("dist" refers to Hamming distane.)A family of codes is locally testable if all members of the family are r-testable for some some constant r. This concept arose from holographic proofs/PCPs. Goldreich and Sudan [GS] asked whether there exist good, locally testable families of codes.In this paper we address the intersection of the two questions stated. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/TIT.2005.851735 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
constant r,good family,testable cyclic code,hamming distance,constant rate,cyclic code,constant normalized distance,condition ii,varepsilon n,linear subspace,testable family,cyclic shift,cyclic linear code,block length n,testable cyclic codes,finite field,block codes,linear code,galois fields,randomized algorithm | Journal | 51 |
Issue | ISSN | Citations |
8 | 0018-9448 | 13 |
PageRank | References | Authors |
0.82 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lászl Babai | 1 | 13 | 0.82 |
| Amir Shpilka | 2 | 1095 | 64.27 |
| Daniel Štefankovic | 3 | 22 | 1.43 |