{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T23:33:54Z","timestamp":1723764834406},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,4,3]],"date-time":"2014-04-03T00:00:00Z","timestamp":1396483200000},"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":[[2014,9]]},"DOI":"10.1007\/s00037-014-0080-5","type":"journal-article","created":{"date-parts":[[2014,4,2]],"date-time":"2014-04-02T05:23:04Z","timestamp":1396416184000},"page":"355-478","source":"Crossref","is-referenced-by-count":4,"title":["Combinatorial PCPs with Efficient Verifiers"],"prefix":"10.1007","volume":"23","author":[{"given":"Or","family":"Meir","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,4,3]]},"reference":[{"key":"80_CR1","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan & Mario Szegedy (1998). Proof verification and Intractability of Approximation Problems. Journal of ACM 45(3), 501\u2013555. Preliminary version in FOCS 1992.","DOI":"10.1145\/278298.278306"},{"key":"80_CR2","doi-asserted-by":"crossref","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.","DOI":"10.1145\/273865.273901"},{"key":"80_CR3","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Leonid A. Levin & Mario Szegedy (1991a). Checking Computations in Polylogarithmic Time. In STOC, 21\u201331.","DOI":"10.1145\/103418.103428"},{"key":"80_CR4","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow & Carsten Lund (1991b). Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 1, 3\u201340.","DOI":"10.1007\/BF01200056"},{"key":"80_CR5","doi-asserted-by":"crossref","unstructured":"Boaz Barak & Oded Goldreich (2002). Universal Arguments and their Applications. In IEEE Conference on Computational Complexity, 194\u2013203.","DOI":"10.1109\/CCC.2002.1004355"},{"key":"80_CR6","doi-asserted-by":"crossref","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.","DOI":"10.1137\/S0097539705446810"},{"key":"80_CR7","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":"80_CR8","doi-asserted-by":"crossref","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.","DOI":"10.1137\/050646445"},{"key":"80_CR9","unstructured":"Peter J. Cameron (1998). Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge CB2 2RU, MA, USA."},{"key":"80_CR10","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":"80_CR11","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."},{"key":"80_CR12","unstructured":"Irit Dinur & Omer Reingold (2006). Assignment testers: Towards combinatorial proof of the PCP theorem. SIAM Journal of Computing 36(4), 155\u2013164."},{"key":"80_CR13","doi-asserted-by":"crossref","unstructured":"Yuri Gurevich & Saharon Shelah (1989). Nearly Linear Time. In Logic at Botik, 108\u2013118.","DOI":"10.1007\/3-540-51237-3_10"},{"key":"80_CR14","unstructured":"F. Thomson Leighton (1992). Introduction to parallel algorithms and architectures: array, trees, hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA."},{"key":"80_CR15","unstructured":"Florence Jessie MacWilliams & Neil James Alexander Sloane (1988). The theory of error correcting codes. Elsevier\/North-Holland, Amsterdam."},{"key":"80_CR16","unstructured":"Or Meir (2011). Combinatorial PCPs with efficient verifiers. Electronic Colloquium on Computational Complexity (ECCC) 18, 104."},{"key":"80_CR17","doi-asserted-by":"crossref","unstructured":"Or Meir (2012). Combinatorial PCPs with Short Proofs. In IEEE Conference on Computational Complexity, 345\u2013355.","DOI":"10.1109\/CCC.2012.14"},{"key":"80_CR18","unstructured":"Alexander Polishchuk & Daniel A. Spielman (1994). Nearly-linear size holographic proofs. In STOC, 194\u2013203."},{"key":"80_CR19","doi-asserted-by":"crossref","unstructured":"Daniel A. Spielman (1996). Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory 42(6), 1723\u20131731.","DOI":"10.1109\/18.556668"},{"key":"80_CR20","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"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0080-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-014-0080-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0080-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,9]],"date-time":"2019-08-09T00:28:59Z","timestamp":1565310539000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-014-0080-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,3]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["80"],"URL":"https:\/\/doi.org\/10.1007\/s00037-014-0080-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4,3]]}}}