On the Robust Testability of Product of Codes
Don Coppersmith, Atri Rudra · Electronic colloquium on computational complexity · 2005
Ben-Sasson and Sudan in [4] 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 [12]. 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.