{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T12:20:51Z","timestamp":1709382051802},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00037-011-0014-4","type":"journal-article","created":{"date-parts":[[2011,8,3]],"date-time":"2011-08-03T05:33:41Z","timestamp":1312349621000},"page":"413-504","source":"Crossref","is-referenced-by-count":13,"title":["PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability"],"prefix":"10.1007","volume":"20","author":[{"given":"Irit","family":"Dinur","sequence":"first","affiliation":[]},{"given":"Eldar","family":"Fischer","sequence":"additional","affiliation":[]},{"given":"Guy","family":"Kindler","sequence":"additional","affiliation":[]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[]},{"given":"Shmuel","family":"Safra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,8,4]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"M. Alekhnovich, S. Buss, S. Moran & T. Pitassi (1998). Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. Manuscript.","DOI":"10.1007\/BFb0055766"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan & Mario Szegedy (1998). Proof verification and the hardness of approximation problems. Journal of the ACM 45(3), 501\u2013555. ISSN 0004-5411.","DOI":"10.1145\/278298.278306"},{"key":"14_CR3","unstructured":"Sanjeev Arora & Shmuel Safra (1998). Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM 45(1), 70\u2013122. ISSN 0004-5411. http:\/\/www.acm.org:80\/pubs\/citations\/journals\/jacm\/1998-45-1\/p70-arora\/ ."},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora & Madhu Sudan (1997). Improved Low Degree Testing and its Applications. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 485\u2013495. El Paso, Texas.","DOI":"10.1145\/258533.258642"},{"key":"14_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai L., Fortnow L., Lund C. (1991) Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1: 3\u201340","journal-title":"Computational Complexity"},{"key":"14_CR6","unstructured":"M. Bellare, S. Goldwasser, C. Lund & A. Russell (1993). Efficient Multi-Prover Interactive Proofs with Applications to Approximation Problems. In Proc. 25th ACM Symp. on Theory of Computing, 113\u2013131."},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"I. Dinur, E. Fischer, G. Kindler, R. Raz & S. Safra (1999). PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. In Proc. 31th ACM Symp. on Theory of Computing.","DOI":"10.1145\/301250.301265"},{"key":"14_CR8","unstructured":"I. Dinur & S. Safra (1998). Monotone-Minimum-Satisfying Assignment is NP-hard for Almost Polynomial Factors. Manuscript."},{"key":"14_CR9","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0020-0190(93)90076-L","volume":"47","author":"J. Hastad","year":"1993","unstructured":"Hastad J., Phillips R., Safra S. (1993) A well-characterized approximation problem. Information Processing Letters 47: 301\u2013305","journal-title":"Information Processing Letters"},{"issue":"5","key":"14_CR10","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"Carsten Lund","year":"1994","unstructured":"Carsten Lund , Mihalis Yannakakis (1994) On the Hardness of Approximating Minimization Problems. Journal of the ACM 41(5): 960\u2013981","journal-title":"Journal of the ACM"},{"key":"14_CR11","unstructured":"R. Raz & S. Safra (1997). A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. In Proc. 29th ACM Symp. on Theory of Computing, 475\u2013484."},{"issue":"3","key":"14_CR12","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 Journal on Computing 27(3): 763\u2013803","journal-title":"SIAM Journal on Computing"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00037-011-0014-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T23:54:59Z","timestamp":1592783699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0014-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,4]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["14"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0014-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8,4]]}}}