Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-070 | 1st May 2011 22:31

Composition of semi-LTCs by two-wise Tensor Products


Authors: Eli Ben-Sasson, Michael Viderman
Publication: 1st May 2011 22:31
Downloads: 1425


In this paper we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the First composition theorem showing that repeating the two-wise tensor operation any constant number of times still results in a locally testable code, improving upon previous results which only worked when the tensor product was applied once.

To obtain our results we define a new tester for tensor products. Our tester uses the distribution of the "inner tester" associated with the base-code to sample rows and columns of the product code. This construction differs from previously studied testers for tensor product codes which sampled rows and columns uniformly.

We show that if the base-code is any LTC or any expander code, then the code obtained by taking the repeated two-wise tensor product of the base-code with itself is locally testable. In particular, this answers a question posed in the paper of Dinur et al. (2006) by expanding the class of allowed base-codes to include all LTCs, and not just so-called uniform LTCs whose associated tester queries all codeword entries with equal probability.

ISSN 1433-8092 | Imprint