{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:52Z","timestamp":1740109492942,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T00:00:00Z","timestamp":1384214400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00037-013-0074-8","type":"journal-article","created":{"date-parts":[[2013,11,11]],"date-time":"2013-11-11T04:14:11Z","timestamp":1384143251000},"page":"601-643","source":"Crossref","is-referenced-by-count":6,"title":["Composition of semi-LTCs by two-wise tensor products"],"prefix":"10.1007","volume":"24","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Viderman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,11,12]]},"reference":[{"issue":"3","key":"74_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"Sanjeev Arora","year":"1998","unstructured":"Arora Sanjeev, Lund Carsten, Motwani Rajeev, Sudan Madhu, Szegedy Mario (1998) Proof Verification and the Hardness of Approximation Problems. Journal of the ACM 45(3): 501\u2013555","journal-title":"Journal of the ACM"},{"issue":"4","key":"74_CR2","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"Eli Ben-Sasson","year":"2006","unstructured":"Ben-Sasson Eli, Goldreich Oded, Harsha Prahladh, Sudan Madhu, Vadhan Salil P. (2006) Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM Journal on Computing 36(4): 889\u2013974","journal-title":"SIAM Journal on Computing"},{"key":"74_CR3","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Prahladh Harsha & Sofya Raskhodnikova (2005). Some 3CNF Properties Are Hard to Test. SIAM Journal on Computing 35(1), 1\u201321. URL http:\/\/epubs.siam.org\/SICOMP\/volume-35\/art_44544.html .","DOI":"10.1137\/S0097539704445445"},{"key":"74_CR4","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Madhu Sudan (2006). Robust locally testable codes and products of codes. Random Struct. Algorithms 28(4), 387\u2013402. URL http:\/\/dx.doi.org\/10.1002\/rsa.20120 .","DOI":"10.1002\/rsa.20120"},{"key":"74_CR5","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Madhu Sudan (2008). Short PCPs with Polylog Query Complexity. SIAM J. Comput 38(2), 551\u2013607. URL http:\/\/dx.doi.org\/10.1137\/050646445 .","DOI":"10.1137\/050646445"},{"key":"74_CR6","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Michael Viderman (2009a). Composition of Semi-LTCs by Two-Wise Tensor Products. In APPROX-RANDOM, Irit Dinur, Klaus Jansen, Joseph Naor & Jos\u00e9 D. P. Rolim, editors, volume 5687 of Lecture Notes in Computer Science, 378\u2013391. Springer. ISBN 978-3-642-03684-2. URL http:\/\/dx.doi.org\/10.1007\/978-3-642-03685-9 .","DOI":"10.1007\/978-3-642-03685-9"},{"key":"74_CR7","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Michael Viderman (2009b). Tensor Products of Weakly Smooth Codes are Robust. Theory of Computing 5(1), 239\u2013255. URL http:\/\/dx.doi.org\/10.4086\/toc.2009.v005a012 .","DOI":"10.4086\/toc.2009.v005a012"},{"key":"74_CR8","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Michael Viderman (2010). Low Rate Is Insufficient for Local Testability. In APPROX-RANDOM, Maria J. Serna, Ronen Shaltiel, Klaus Jansen & Jos\u00e9 D. P. Rolim, editors, volume 6302 of Lecture Notes in Computer Science, 420\u2013433. Springer. ISBN 978-3-642-15368-6. URL http:\/\/dx.doi.org\/10.1007\/978-3-642-15369-3 .","DOI":"10.1007\/978-3-642-15369-3"},{"issue":"3","key":"74_CR9","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1109\/TIT.2004.824917","volume":"50","author":"Bennatan Amir","year":"2004","unstructured":"Amir Bennatan, David Burshtein (2004) On the Application of LDPC Codes to Arbitrary Discrete-Memoryless Channels. IEEE Transactions on Information Theory 50(3): 417\u2013438","journal-title":"IEEE Transactions on Information Theory"},{"key":"74_CR10","unstructured":"M. Blum M. Luby & R. Rubinfeld (1993). Self-Testing\/Correcting with Applications to Numerical Problems. JCSS: Journal of Computer and System Sciences 47."},{"key":"74_CR11","unstructured":"Don Coppersmith & Atri Rudra (2005). On the Robust Testability of Product of Codes. Electronic Colloquium on Computational Complexity (ECCC) (104). URL http:\/\/eccc.hpi-web.de\/eccc-reports\/2005\/TR05-104\/index.html ."},{"key":"74_CR12","unstructured":"Irit Dinur (2007). The PCP theorem by gap amplification. Journal of the ACM 54(3), 12:1\u201312:44. ISSN 0004-5411."},{"key":"74_CR13","doi-asserted-by":"crossref","unstructured":"Irit Dinur & Omer Reingold (2006). Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. SIAM Journal on Computing 36(4), 975\u20131024. URL http:\/\/dx.doi.org\/10.1137\/S0097539705446962 .","DOI":"10.1137\/S0097539705446962"},{"key":"74_CR14","doi-asserted-by":"crossref","unstructured":"Irit Dinur, Madhu Sudan & Avi Wigderson (2006). Robust Local Testability of Tensor Products of LDPC Codes. In APPROX-RANDOM, volume 4110 of Lecture Notes in Computer Science, 304\u2013315. Springer. ISBN 3-540-38044-2. URL http:\/\/dx.doi.org\/10.1007\/11830924_29 .","DOI":"10.1007\/11830924_29"},{"key":"74_CR15","doi-asserted-by":"crossref","unstructured":"R. G. Gallager (1963). Low-density Parity Check Codes. MIT Press.","DOI":"10.7551\/mitpress\/4347.001.0001"},{"key":"74_CR16","volume-title":"Information Theory and Reliable Communication","author":"R.G. Gallager","year":"1968","unstructured":"Gallager R.G. (1968) Information Theory and Reliable Communication. Wiley, New York"},{"key":"74_CR17","unstructured":"Oded Goldreich (2005). Short Locally Testable Codes and Proofs (Survey). Electronic Colloquium on Computational Complexity (ECCC) (014). URL http:\/\/eccc.hpi-web.de\/eccc-reports\/2005\/TR05-014\/index.html ."},{"key":"74_CR18","unstructured":"Oded Goldreich & Or Meir (2007). The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable. Electronic Colloquium on Computational Complexity (ECCC) 14(062). URL http:\/\/eccc.hpi-web.de\/eccc-reports\/2007\/TR07-062\/index.html ."},{"key":"74_CR19","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Madhu Sudan (2006). Locally testable codes and PCPs of almost-linear length. Journal of the ACM 53(4), 558\u2013655. ISSN 0004-5411.","DOI":"10.1145\/1162349.1162351"},{"key":"74_CR20","unstructured":"Tali Kaufman & Madhu Sudan (2007). Sparse Random Linear Codes are Locally Decodable and Testable. In FOCS, 590\u2013600. IEEE Computer Society. URL http:\/\/doi.ieeecomputersociety.org\/10.1109\/FOCS.2007.65 ."},{"key":"74_CR21","unstructured":"Tali Kaufman & Madhu Sudan (2008). Algebraic property testing: the role of invariance. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, 403\u2013412. ACM. ISBN 978-1-60558-047-0. URL http:\/\/doi.acm.org\/10.1145\/1374376.1374434 ."},{"key":"74_CR22","doi-asserted-by":"crossref","unstructured":"Tali Kaufman & Michael Viderman (2010). Locally Testable vs. Locally Decodable Codes. In APPROX-RANDOM, Maria J. Serna, Ronen Shaltiel, Klaus Jansen & Jos\u00e9 D. P. Rolim, editors, volume 6302 of Lecture Notes in Computer Science, 670\u2013682. Springer. ISBN 978-3-642-15368-6. URL http:\/\/dx.doi.org\/10.1007\/978-3-642-15369-3 .","DOI":"10.1007\/978-3-642-15369-3"},{"key":"74_CR23","unstructured":"Swastik Kopparty & Shubhangi Saraf (2010). Local list-decoding and testing of random linear codes from high error. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, Leonard J. Schulman, editor, 417\u2013426. ACM. ISBN 978-1-4503-0050-6. URL http:\/\/doi.acm.org\/10.1145\/1806689.1806748 ."},{"key":"74_CR24","unstructured":"Swastik Kopparty, Shubhangi Saraf & Sergey Yekhanin (2010). High-rate codes with sublinear-time decoding. In ECCC - TR10-148. URL http:\/\/eccc.hpi-web.de\/report\/2010\/148\/ ."},{"key":"74_CR25","doi-asserted-by":"crossref","unstructured":"Grigori\u012d A. Margulis (1982). Explicit constructions of graphs without short cycles and low density codes. Combinatorica 2(1), 71\u201378.","DOI":"10.1007\/BF02579283"},{"key":"74_CR26","doi-asserted-by":"crossref","unstructured":"Or Meir (2009). Combinatorial Construction of Locally Testable Codes. SIAM J. Comput 39(2), 491\u2013544. URL http:\/\/dx.doi.org\/10.1137\/080729967 .","DOI":"10.1137\/080729967"},{"key":"74_CR27","doi-asserted-by":"crossref","unstructured":"Michael Sipser & Daniel A. Spielman (1996). Expander Codes. IEEE Transactions on Information Theory 42(6), 1710\u20131722. Preliminary version appeared in FOCS 1994.","DOI":"10.1109\/18.556667"},{"key":"74_CR28","unstructured":"Luca Trevisan (2004). Some Applications of Coding Theory in Computational Complexity. In ECCC: Electronic Colloquium on Computational Complexity, technical reports."},{"key":"74_CR29","doi-asserted-by":"crossref","unstructured":"Paul Valiant (2005). The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. In APPROX-RANDOM, volume 3624 of Lecture Notes in Computer Science, 472\u2013481. Springer. ISBN 3-540-28239-4. URL http:\/\/dx.doi.org\/10.1007\/11538462_40 .","DOI":"10.1007\/11538462_40"},{"key":"74_CR30","doi-asserted-by":"crossref","unstructured":"Michael Viderman (2012).A Combination of Testability and Decodability by Tensor Products. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, Anupam Gupta, Klaus Jansen, Jos\u00e9 D. P. Rolim & Rocco A. Servedio, editors, volume 7408 of Lecture Notes in Computer Science, 651\u2013662. Springer. ISBN 978-3-642-32511-3. URL http:\/\/dx.doi.org\/10.1007\/978-3-642-32512-0 .","DOI":"10.1007\/978-3-642-32512-0"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0074-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-013-0074-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0074-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T08:01:52Z","timestamp":1564646512000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-013-0074-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,12]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["74"],"URL":"https:\/\/doi.org\/10.1007\/s00037-013-0074-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2013,11,12]]}}}