We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

Inspired by recent construction of high-rate locally correctable codes with sublinear query complexity due to
Kopparty, Saraf and Yekhanin (2010) we address the similar question for locally testable codes (LTCs).

In this note we show a construction of high-rate LTCs with sublinear query complexity.
More formally, we show that for ... more >>>

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, ... more >>>

Ben-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 ... more >>>

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a randomized algorithm (tester) that makes at most $q$ queries to the input word. This algorithm accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot ... more >>>