ECCC-Report TR11-087https://eccc.weizmann.ac.il/report/2011/087Comments and Revisions published for TR11-087en-usSun, 10 Jun 2012 19:09:35 +0300
Revision 3
| A Combination of Testability and Decodability by Tensor Products |
Michael Viderman
https://eccc.weizmann.ac.il/report/2011/087#revision3Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as a black box) to present a combinatorial construction of locally testable codes that match best known parameters. As a consequence, this construction was obtained over sufficiently large fields.
In this paper we improve the result of Ben-Sasson and Sudan and show that for \emph{any} linear codes the associated tensor products are locally testable. Consequently, the construction of Meir can be taken over any field, including the binary field.
Moreover, a combination of our result with the result of Spielman (IEEE IT, 1996) implies a construction of linear codes (over any field) that combine the following properties:
\begin{itemize}
\item have constant rate and constant relative distance;
\item have blocklength $n$ and testable with $n^{\epsilon}$ queries, for any constant $\epsilon > 0$;
\item linear time encodable and linear-time decodable from a constant fraction of errors.
\end{itemize}
Furthermore, a combination of our result with the result of Guruswami et al. (STOC 2009) implies a similar corollary regarding the list-decodable codes.Sun, 10 Jun 2012 19:09:35 +0300https://eccc.weizmann.ac.il/report/2011/087#revision3
Revision 2
| A Combination of Testability and Decodability by Tensor Products |
Michael Viderman
https://eccc.weizmann.ac.il/report/2011/087#revision2Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as a black box) to present a combinatorial construction of locally testable codes that match best known parameters. As a consequence, this construction was obtained over sufficiently large fields.
In this paper we improve the result of Ben-Sasson and Sudan and show that for \emph{any} linear codes the associated tensor products are locally testable. Consequently, the construction of Meir can be taken over any field, including the binary field.
Moreover, a combination of our result with the result of Spielman (IEEE IT, 1996) implies a construction of linear codes (over any field) that combine the following properties:
\begin{itemize}
\item have constant rate and constant relative distance;
\item have blocklength $n$ and testable with $n^{\epsilon}$ queries, for any constant $\epsilon > 0$;
\item linear time encodable and linear-time decodable from a constant fraction of errors.
\end{itemize}
Furthermore, a combination of our result with the result of Guruswami et al. (STOC 2009) implies a similar corollary regarding the list-decodable codes.Sun, 06 Nov 2011 18:51:34 +0200https://eccc.weizmann.ac.il/report/2011/087#revision2
Revision 1
| A Combination of Testability and Decodability by Tensor Products |
Michael Viderman
https://eccc.weizmann.ac.il/report/2011/087#revision1Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be
applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as a black box) to present a combinatorial construction of locally testable codes that match best known parameters. As a consequence,
this construction was obtained over sufficiently large fields.
In this paper we improve the result of Ben-Sasson and Sudan and show that for \emph{any} linear codes the associated tensor products are locally testable. Consequently, the construction of Meir can be taken over any field, including the binary field.
Moreover, a combination of our result with the result of Spielman (IEEE IT, 1996) implies a construction of linear codes (over any field) that combine the following properties:
\begin{itemize}
\item have constant rate and constant relative distance;
\item have blocklength $n$ and testable with $n^{\epsilon}$ queries, for any constant $\epsilon > 0$;
\item linear time encodable and linear-time decodable from a constant fraction of errors.
\end{itemize}
Furthermore, a combination of our result with the result of Guruswami et al. (STOC 2009) implies a similar corollary regarding the list-decodable codes.Wed, 03 Aug 2011 19:31:24 +0300https://eccc.weizmann.ac.il/report/2011/087#revision1
Paper TR11-087
| A Combination of Testability and Decodability by Tensor Products |
Michael Viderman
https://eccc.weizmann.ac.il/report/2011/087Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as a black box) to present a combinatorial construction of locally testable codes that match best known parameters. As a consequence, this construction was obtained over sufficiently large fields.
In this paper we improve the result of Ben-Sasson and Sudan and show that for \emph{any} linear codes the associated tensor products are locally testable. Consequently, the construction of Meir can be taken over any field, including the binary field.
Moreover, a combination of our result with the result of Spielman (IEEE IT, 1996) implies a construction of linear codes (over any field) that combine the following properties:
\begin{itemize}
\item have constant rate and constant relative distance;
\item have blocklength $n$ and testable with $n^{\epsilon}$ queries, for any constant $\epsilon > 0$;
\item linear time encodable and linear-time decodable from a constant fraction of errors.
\end{itemize}
Furthermore, a combination of our result with the result of Guruswami et al. (STOC 2009) implies a similar corollary regarding the list-decodable codes.Fri, 03 Jun 2011 22:41:53 +0300https://eccc.weizmann.ac.il/report/2011/087