{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T16:03:23Z","timestamp":1780934603497,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705826","type":"print"},{"value":"9783540705833","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_44","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"536-547","source":"Crossref","is-referenced-by-count":48,"title":["Interactive PCP"],"prefix":"10.1007","author":[{"given":"Yael Tauman","family":"Kalai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"3","key":"44_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof Verification and Hardness of Approximation Problems. J. ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"44_CR2","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"44_CR3","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S. Arora","year":"2003","unstructured":"Arora, S., Sudan, M.: Improved Low-Degree Testing and its Applications. Combinatorica\u00a023(3), 365\u2013426 (2003)","journal-title":"Combinatorica"},{"key":"44_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity\u00a01, 3\u201340 (1991)","journal-title":"Computational Complexity"},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions. In: STOC 1988, pp. 113\u2013131 (1988)","DOI":"10.1145\/62212.62223"},{"issue":"2","key":"44_CR6","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes. J. Comput. Syst. Sci.\u00a036(2), 254\u2013276 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"44_CR7","doi-asserted-by":"crossref","unstructured":"Beigel, R.: The Polynomial Method in Circuit Complexity. In: Structure in Complexity Theory Conference, pp. 82\u201395 (1993)","DOI":"10.1109\/SCT.1993.336538"},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"Dinur, I., Fischer, E., Kindler, G., Raz, R., Safra, S.: PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. In: STOC 1999, pp. 29\u201340 (1999)","DOI":"10.1145\/301250.301265"},{"issue":"2","key":"44_CR9","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lovasz, L., Safra, S., Szegedy, M.: Interactive Proofs and the Hardness of Approximating Cliques. J. ACM\u00a043(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"key":"44_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U., Lovasz, L.: Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract). In: STOC 1992, pp. 733\u2013744 (1992)","DOI":"10.1145\/129712.129783"},{"key":"44_CR11","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of Instance Compression and Succinct PCPs for NP. In: STOC 2008 (2008)","DOI":"10.1145\/1374376.1374398"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.: Delegating Computation: Interactive Proofs for Mortals. In: STOC 2008 (2008)","DOI":"10.1145\/1374376.1374396"},{"issue":"1","key":"44_CR13","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing\u00a018(1), 186\u2013208 (1989)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"44_CR14","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. J. ACM\u00a038(3), 691\u2013729 (1991)","journal-title":"J. ACM"},{"key":"44_CR15","doi-asserted-by":"crossref","unstructured":"Harnik, H., Naor, M.: On the Compressibility of NP instances and Cryptographic Applications. In: FOCS, pp. 719\u2013728 (2006)","DOI":"10.1109\/FOCS.2006.54"},{"key":"44_CR16","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-Knowledge from Secure Muliparty Computation. In: STOC 2007, pp. 21\u201330 (2007)","DOI":"10.1145\/1250790.1250794"},{"key":"44_CR17","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Raz, R.: Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. In: FOCS 2006, pp. 355\u2013366 (2006)","DOI":"10.1109\/FOCS.2006.74"},{"key":"44_CR18","unstructured":"Kalai, Y.T., Raz, R.: Probabilistically Checkable Arguments"},{"key":"44_CR19","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC 1992, pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"issue":"4","key":"44_CR20","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic Methods for Interactive Proof Systems. J. ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"J. ACM"},{"key":"44_CR21","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Sub-Constant Error Low Degree Test of Almost Linear Size. In: STOC 2006, pp. 21\u201330 (2006)","DOI":"10.1145\/1132516.1132520"},{"key":"44_CR22","doi-asserted-by":"crossref","unstructured":"Micali, S.: CS Proofs (Extended Abstracts). In: FOCS 1994, pp. 436\u2013453 (1994)","DOI":"10.1109\/SFCS.1994.365746"},{"key":"44_CR23","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. In: STOC 1997, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"issue":"4","key":"44_CR24","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A. Razborov","year":"1987","unstructured":"Razborov, A.: Lower Bounds for the Size of Circuits of Bounded Depth with Basis {\u2009\u2227\u2009,\u2009\u2295\u2009}. Math. Notes of the Academy of Science of the USSR\u00a041(4), 333\u2013338 (1987)","journal-title":"Math. Notes of the Academy of Science of the USSR"},{"key":"44_CR25","doi-asserted-by":"crossref","unstructured":"Raz, R.: Quantum Information and the PCP Theorem. In: FOCS 2005, pp. 459\u2013468 (2005)","DOI":"10.1109\/SFCS.2005.62"},{"issue":"4","key":"44_CR26","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP=PSPACE. J. ACM\u00a039(4), 869\u2013877 (1992)","journal-title":"J. ACM"},{"key":"44_CR27","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In: STOC 1987, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70583-3_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:13:29Z","timestamp":1738325609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}