{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,29]],"date-time":"2023-08-29T22:58:01Z","timestamp":1693349881967},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,1,21]],"date-time":"2016-01-21T00:00:00Z","timestamp":1453334400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s00037-015-0111-x","type":"journal-article","created":{"date-parts":[[2016,1,21]],"date-time":"2016-01-21T04:11:04Z","timestamp":1453349464000},"page":"1-102","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Combinatorial PCPs with Short Proofs"],"prefix":"10.1007","volume":"25","author":[{"given":"Or","family":"Meir","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,21]]},"reference":[{"issue":"3","key":"111_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora, Carsten Lund, Rajeev Motwani, MadhuSudan Mario Szegedy (1998) Proof verification and Intractability of Approximation Problems. Journal of ACM 45(3): 501\u2013555 Preliminary version in FOCS 1992","journal-title":"Journal of ACM"},{"issue":"1","key":"111_CR2","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora, Shmuel Safra (1998) Probabilistic Checkable Proofs: A New Characterization of NP. Journal of ACM volume 45(1): 70\u2013122 Preliminary version in FOCS 1992","journal-title":"Journal of ACM volume"},{"key":"111_CR3","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Leonid A. Levin & Mario Szegedy (1991). Checking Computations in Polylogarithmic Time. In STOC, 21\u201331.","DOI":"10.1145\/103418.103428"},{"issue":"4","key":"111_CR4","first-page":"120","volume":"36","author":"Ben-Sasson Eli","year":"2006","unstructured":"Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan (2006) Robust PCPs of Proximity, Shorter PCPs and Applications to Coding. SIAM Journal of Computing 36(4): 120\u2013134","journal-title":"SIAM Journal of Computing"},{"key":"111_CR5","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan & Salil P. Vadhan (2005). Short PCPs Verifiable in Polylogarithmic Time. In IEEE Conference on Computational Complexity, 120\u2013134.","DOI":"10.1109\/CCC.2005.27"},{"key":"111_CR6","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Prahladh Harsha, Oded Lachish & Arie Matsliah (2009). Sound 3-Query PCPPs Are Long. TOCT 1(2).","DOI":"10.1145\/1595391.1595394"},{"key":"111_CR7","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir & Henning Stichtenoth (2013). Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity. In FOCS, 320\u2013329. Available as ECCC TR13-085.","DOI":"10.1109\/FOCS.2013.42"},{"issue":"4","key":"111_CR8","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1002\/rsa.20120","volume":"28","author":"Ben-Sasson Eli","year":"2006","unstructured":"Eli Ben-Sasson, Madhu Sudan (2006) Robust locally testable codes and products of codes. Random Struct. Algorithms 28(4): 387\u2013402 Preliminary version in APPROX-RANDOM 2004","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"111_CR9","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/050646445","volume":"38","author":"Ben-Sasson Eli","year":"2008","unstructured":"Eli Ben-Sasson, Madhu Sudan (2008) Short PCPs with Polylog Query Complexity. SIAM J. Comput. 38(2): 551\u2013607 Preliminary version in STOC 2005","journal-title":"SIAM J. Comput."},{"key":"111_CR10","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Michael Viderman (2009a). Composition of Semi-LTCs by Two-Wise Tensor Products. In APPROX-RANDOM, 378\u2013391.","DOI":"10.1007\/978-3-642-03685-9_29"},{"issue":"1","key":"111_CR11","doi-asserted-by":"crossref","first-page":"239","DOI":"10.4086\/toc.2009.v005a012","volume":"5","author":"Ben-Sasson Eli","year":"2009","unstructured":"Eli Ben-Sasson, Michael Viderman (2009b) Tensor Products of Weakly Smooth Codes are Robust. Theory of Computing 5(1): 239\u2013255","journal-title":"Theory of Computing"},{"key":"111_CR12","doi-asserted-by":"crossref","unstructured":"Stephen A. Cook (1971). The Complexity of Theorem-Proving Procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"111_CR13","doi-asserted-by":"crossref","unstructured":"Irit Dinur (2007). The PCP theorem by Gap Amplification. Journal of ACM 54(3), 241\u2013250. Preliminary version in STOC 2006.","DOI":"10.1145\/1236457.1236459"},{"key":"111_CR14","doi-asserted-by":"crossref","unstructured":"Irit Dinur & Or Meir (2010). Derandomized Parallel Repetition of Structured PCPs. In IEEE Conference on Computational Complexity, 16\u201327. Full version can be obtained as ECCC TR10-107.","DOI":"10.1109\/CCC.2010.11"},{"key":"111_CR15","doi-asserted-by":"crossref","unstructured":"Irit Dinur & Omer Reingold (2006). Assignment testers: Towards combinatorial proof of the PCP theorem. SIAM Journal of Computing 36(4), 155\u2013164.","DOI":"10.1137\/S0097539705446962"},{"key":"111_CR16","doi-asserted-by":"crossref","unstructured":"Irit Dinur, Madhu Sudan & Avi Wigderson (2006). Robust local testability of tensor products of LDPC codes. In APPROX-RANDOM, 304\u2013315.","DOI":"10.1007\/11830924_29"},{"key":"111_CR17","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Dana Ron (2002). Property Testing in Bounded Degree Graphs. Algorithmica 32(2), 302\u2013343.","DOI":"10.1007\/s00453-001-0078-7"},{"key":"111_CR18","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Shmuel Safra (2000). A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. SIAM J. Comput. 29(4), 1132\u20131154.","DOI":"10.1137\/S0097539797315744"},{"key":"111_CR19","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Madhu Sudan (2006). Locally testable codes and PCPs of almost linear length. Journal of ACM 53(4), 558\u2013655. Preliminary version in FOCS 2002, pages 13\u201322.","DOI":"10.1145\/1162349.1162351"},{"key":"111_CR20","unstructured":"Rolf K\u00f6tter (1992). A Unified Description of an Error Locating Procedure for Linear Codes. In Proceedings of the International Workshop on Algebraic and Combinatorial Coding Theory, 113\u2013117."},{"key":"111_CR21","unstructured":"F. Thomson Leighton (1992). Introduction to parallel algorithms and architectures: array, trees, hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA."},{"key":"111_CR22","unstructured":"Florence Jessie MacWilliams & Neil James Alexander Sloane (1988). The theory of error-correcting codes. Elsevier\/North-Holland, Amsterdam."},{"key":"111_CR23","doi-asserted-by":"crossref","unstructured":"Or Meir (2009). Combinatorial PCPs with Efficient Verifiers. In FOCS, 463\u2013471. To appear in Computational Complexity. A more elaborated version is available as ECCC TR11-104.","DOI":"10.1109\/FOCS.2009.10"},{"key":"111_CR24","doi-asserted-by":"crossref","unstructured":"Or Meir (2013). IP = PSPACE Using Error-Correcting Codes. SIAM J. Comput. 42(1), 380\u2013403.","DOI":"10.1137\/110829660"},{"key":"111_CR25","doi-asserted-by":"crossref","unstructured":"Christos H. Papadimitriou & Mihalis Yannakakis (1991). Optimization, Approximation, and Complexity Classes. J. Comput. Syst. Sci. 43(3), 425\u2013440.","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"111_CR26","doi-asserted-by":"crossref","unstructured":"Ruud Pellikaan (1992). On decoding by error location and dependent sets of error positions. Discrete Mathematics 106-107, 369\u2013381.","DOI":"10.1016\/0012-365X(92)90567-Y"},{"key":"111_CR27","doi-asserted-by":"crossref","unstructured":"Nicholas Pippenger & Michael J. Fischer (1979). Relations Among Complexity Measures. J. ACM 26(2), 361\u2013381.","DOI":"10.1145\/322123.322138"},{"key":"111_CR28","doi-asserted-by":"crossref","unstructured":"Alexander Polishchuk & Daniel A. Spielman (1994). Nearly-linear size holographic proofs. In STOC, 194\u2013203.","DOI":"10.1145\/195058.195132"},{"key":"111_CR29","doi-asserted-by":"crossref","unstructured":"Michael Sipser & Daniel A. Spielman (1996). Expander codes. IEEE Transactions on Information Theory 42(6), 1710\u20131722.","DOI":"10.1109\/18.556667"},{"key":"111_CR30","unstructured":"Madhu Sudan (2001). Algorithmic introduction to coding theory (Lecture notes). Available from http:\/\/theory.csail.mit.edu\/~madhu\/FT01\/ ."},{"key":"111_CR31","doi-asserted-by":"crossref","unstructured":"Mario Szegedy (1999). Many-Valued Logics and Holographic Proofs. In ICALP, 676\u2013686.","DOI":"10.1007\/3-540-48523-6_64"},{"key":"111_CR32","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (1977). Graph-Theoretic Arguments in Low-Level Complexity. In MFCS, 162\u2013176.","DOI":"10.1007\/3-540-08353-7_135"},{"key":"111_CR33","unstructured":"Michael Viderman (2011). A Combination of Testability and Decodability by Tensor Products. Electronic Colloquium on Computational Complexity (ECCC) 18, 87."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0111-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0111-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0111-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:01:59Z","timestamp":1558522919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0111-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,21]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["111"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0111-x","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,21]]}}}