期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
