{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:19:40Z","timestamp":1781259580520,"version":"3.54.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s00037-011-0013-5","type":"journal-article","created":{"date-parts":[[2011,5,25]],"date-time":"2011-05-25T05:34:43Z","timestamp":1306301683000},"page":"207-327","source":"Crossref","is-referenced-by-count":17,"title":["Derandomized Parallel Repetition via Structured PCPs"],"prefix":"10.1007","volume":"20","author":[{"given":"Irit","family":"Dinur","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Or","family":"Meir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2011,5,26]]},"reference":[{"key":"13_CR1","unstructured":"Sanjeev Arora , Carsten Lund (1996). Hardness of Approximations. PW Publishing."},{"issue":"3","key":"13_CR2","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, Madhu Sudan, 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":"13_CR3","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"},{"issue":"3","key":"13_CR4","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"Arora Sanjeev","year":"2003","unstructured":"Sanjeev Arora, Madhu Sudan (2003) Improved Low-Degree Testing and its Applications. Combinatorica 23(3): 365\u2013426","journal-title":"Combinatorica"},{"key":"13_CR5","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy (1991). Checking Computations in Polylogarithmic Time. In STOC, 21\u201331"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Mihir Bellare, Shafi Goldwasser, Carsten Lund, Alexander Russell (1993). Efficient probabilistically checkable proofs and applications to approximations. In STOC, 294\u2013304.","DOI":"10.1145\/167088.167174"},{"issue":"4","key":"13_CR7","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":"13_CR8","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":"13_CR9","volume-title":"Combinatorics: Topics, Techniques, Algorithms","author":"Cameron Peter J.","year":"1998","unstructured":"Peter J. Cameron (1998) Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge CB2 2RU, MA, USA"},{"issue":"3","key":"13_CR10","first-page":"241","volume":"54","author":"Dinur Irit","year":"2007","unstructured":"Irit Dinur (2007) The PCP Theorem by Gap Amplification. Journal of ACM 54(3): 241\u2013250 Preliminary version in STOC 2006","journal-title":"Journal of ACM"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra (1999). PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. In STOC, 29\u201340.","DOI":"10.1145\/301250.301265"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Irit Dinur, Elazar Goldenberg (2008). Locally Testing Direct Product in the Low Error Range. In FOCS, 613\u2013622.","DOI":"10.1109\/FOCS.2008.26"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Irit Dinur, Praladh Harsha (2009). Composition of low-error 2-query PCPs using decodable PCPs. In FOCS.","DOI":"10.1109\/FOCS.2009.8"},{"key":"13_CR14","unstructured":"Irit Dinur, Or Meir (2010). Derandomized Parallel Repetition via Structured PCPs. In CCC."},{"issue":"4","key":"13_CR15","first-page":"155","volume":"36","author":"Dinur Irit","year":"2006","unstructured":"Irit Dinur, Omer Reingold (2006) Assignment testers: Towards combinatorial proof of the PCP theorem. SIAM Journal of Computing 36(4): 155\u2013164","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"13_CR16","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"Feige Uriel","year":"1996","unstructured":"Uriel Feige, Shafi Goldwasser, L\u00e1szl\u00f3 Lov\u00e1sz, Shmuel Safra, Mario Szegedy (1996) Interactive Proofs and the Hardness of Approximating Cliques. J. ACM 43(2): 268\u2013292","journal-title":"J. ACM"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Uriel Feige, Joe Kilian (1995). Impossibility results for recycling random bits in two-prover proof systems. In STOC, 457\u2013468.","DOI":"10.1145\/225058.225183"},{"issue":"4","key":"13_CR18","doi-asserted-by":"crossref","first-page":"1132","DOI":"10.1137\/S0097539797315744","volume":"29","author":"Goldreich Oded","year":"2000","unstructured":"Oded Goldreich, Shmuel Safra (2000) A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. SIAM J. Comput. 29(4): 1132\u20131154","journal-title":"SIAM J. Comput."},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson (2008). Uniform direct product theorems: simplified, optimized, and derandomized. In STOC, 579\u2013588.","DOI":"10.1145\/1374376.1374460"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Valentine Kabanets, Avi Wigderson (2009). New direct-product testers and 2-query PCPs. In STOC, 131\u2013140.","DOI":"10.1145\/1536414.1536435"},{"issue":"4","key":"13_CR21","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"Khot Subhash","year":"2006","unstructured":"Subhash Khot (2006) Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique. SIAM J. Comput. 36(4): 1025\u20131071","journal-title":"SIAM J. Comput."},{"key":"13_CR22","volume-title":"Introduction to parallel algorithms and architectures: array, trees, hypercubes","author":"F. Thomson Leighton","year":"1992","unstructured":"Thomson Leighton F. (1992) Introduction to parallel algorithms and architectures: array, trees, hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA"},{"issue":"3","key":"13_CR23","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"Lubotzky Alexander","year":"1988","unstructured":"Alexander Lubotzky, R. Phillips, P. Sarnak (1988) Ramanujan graphs. Combinatorica 8(3): 261\u2013277","journal-title":"Combinatorica"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Or Meir (2009). Combinatorial PCPs with efficient verifiers. In FOCS.","DOI":"10.1109\/FOCS.2009.10"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Dana Moshkovitz, Ran Raz (2008). Two Query PCP with Sub-Constant Error. In FOCS. Full version is available as ECCC TR08-071.","DOI":"10.1109\/FOCS.2008.60"},{"issue":"3","key":"13_CR26","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"Papadimitriou Christos H.","year":"1991","unstructured":"Christos H. Papadimitriou, Mihalis Yannakakis (1991) Optimization, Approximation, and Complexity Classes. J. Comput. Syst. Sci. 43(3): 425\u2013440","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR27","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"},{"issue":"3","key":"13_CR28","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"Raz Ran","year":"1998","unstructured":"Ran Raz (1998) A Parallel Repetition Theorem. SIAM J. Comput. 27(3): 763\u2013803","journal-title":"SIAM J. Comput."},{"key":"13_CR29","doi-asserted-by":"crossref","unstructured":"Ran Raz, Shmuel Safra (1997). A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. In STOC, 475\u2013484.","DOI":"10.1145\/258533.258641"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00037-011-0013-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T00:45:45Z","timestamp":1560213945000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0013-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,26]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["13"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0013-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,26]]}}}