Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-130 | 24th August 2010 00:17

Locally Testable vs. Locally Decodable Codes

RSS-Feed




Revision #1
Authors: Tali Kaufman, Michael Viderman
Accepted on: 24th August 2010 00:17
Downloads: 2286
Keywords: 


Abstract:

We study the relation between locally testable and locally decodable codes.
Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Locally decodable codes (LDCs) allow to recover each message entry with high probability by reading only a few entries of a slightly corrupted codeword. A linear code $\C \subseteq \F_2^n$ is called sparse if $n \geq 2^{\Omega(\dim(\C))}$.

It is well-known that LTCs do not imply LDCs and that there is an intersection between these two families. E.g. the Hadamard code is both LDC and LTC. However, it was not known whether LDC implies LTC. We show the following results.
\begin{itemize}
\item Two-transitive codes with a local constraint imply LDCs,
while they do not imply LTCs.

\item Every non-sparse LDC contains a large subcode which is not LTC, while every subcode of an LDC remains LDC. Hence, every non-sparse LDC contains a subcode that is LDC but is not LTC.
\end{itemize}
The above results demonstrate inherent differences between LDCs and LTCs, in particular, they imply that LDCs do not imply LTCs.



Changes to previous version:

some typos were fixed


Paper:

TR10-130 | 18th August 2010 01:16

Locally Testable vs. Locally Decodable Codes





TR10-130
Authors: Tali Kaufman, Michael Viderman
Publication: 18th August 2010 03:39
Downloads: 1129
Keywords: 


Abstract:

We study the relation between locally testable and locally decodable codes.
Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Locally decodable codes (LDCs) allow to recover each message entry with high probability by reading only a few entries of a slightly corrupted codeword. A linear code $\C \subseteq \F_2^n$ is called sparse if $n \geq 2^{\Omega(\dim(\C))}$.

It is well-known that LTCs do not imply LDCs and that there is an intersection between these two families. E.g. the Hadamard code is both LDC and LTC. However, it was not known whether LDC implies LTC. We show the following results.
\begin{itemize}
\item Two-transitive codes with a local constraint imply LDCs,
while they do not imply LTCs.

\item Every non-sparse LDC contains a large subcode which is not LTC, while every subcode of an LDC remains LDC. Hence, every non-sparse LDC contains a subcode that is LDC but is not LTC.
\end{itemize}
The above results demonstrate inherent differences between LDCs and LTCs, in particular, they imply that LDCs do not imply LTCs.



ISSN 1433-8092 | Imprint