Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-104 | 16th September 2005 00:00

On the Robust Testability of Product of Codes



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