Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-104 | 16th September 2005 00:00

#### On the Robust Testability of Product of Codes

TR05-104
Authors: Don Coppersmith, Atri Rudra
Publication: 22nd September 2005 15:04
Downloads: 3144
Keywords:

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