ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-104 | 16th September 2005 00:00

On the Robust Testability of Product of Codes

RSS-Feed

Abstract:

Ben-Sasson and Sudan in~\cite{BS04} asked if the following test
is robust for the tensor product of a code with another code--
pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that for general linear codes, the test is not robust~\cite{V05}.
However the question remained open for the tensor
product of a code with itself. We resolve this question in the
negative. We also show a similar result for non-linear codes.



ISSN 1433-8092 | Imprint