{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T02:20:52Z","timestamp":1743128452754,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662242"},{"type":"electronic","value":"9783540485230"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48523-6_64","type":"book-chapter","created":{"date-parts":[[2007,12,10]],"date-time":"2007-12-10T12:06:31Z","timestamp":1197288391000},"page":"676-686","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Many-Valued Logics and Holographic Proofs"],"prefix":"10.1007","author":[{"given":"Mario","family":"Szegedy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,1,18]]},"reference":[{"key":"64_CR1","unstructured":"S. Arora and C. Lund, Hardness of approximations. In Approximation Algorithms for NP-hard problems, D. Hochbaum, ed. PWS Publishing, 1996."},{"key":"64_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C, Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and the intractability of approximation problems. Proceedings of the 33rd\n Symposium on Foundations of Computer Science, IEEE 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"64_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. To appear Journal of the ACM. Preliminary version in Proceedings of the Thirty Third Annual Symposium on the Foundations of Computer Science, IEEE, 1992.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"64_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow, and C. Lund, Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3\u201340, 1991.","journal-title":"Computational Complexity"},{"key":"64_CR5","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin, and M. Szegedy, Checking computations in polylogarithmic time. Proceedings of the Twenty Third Annual Symposium on the Theory of Computing, ACM, 1991.","DOI":"10.1145\/103418.103428"},{"key":"64_CR6","unstructured":"L. Babai and K. Friedl, On slightly superlinear transparent proofs. Univ. Chicago Tech. Report, CS-93-13, 1993."},{"issue":"2","key":"64_CR7","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra, and M. Szegedy, Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268\u2013292, March 1996.","journal-title":"Journal of the ACM"},{"issue":"2","key":"64_CR8","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/0304-3975(94)90251-8","volume":"134","author":"L. Fortnow","year":"1994","unstructured":"L. Fortnow, J. Rompel, and M. Sipser, On the power of multi-prover interactive protocols. Theoretical Computer Science, 134(2):545\u2013557, November 1994.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"64_CR9","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof-systems. SIAM J. on Computing, 18(1):186\u2013208, February 1989.","journal-title":"SIAM J. on Computing"},{"key":"64_CR10","doi-asserted-by":"crossref","unstructured":"A. Polishchuk and D. Spielman, Nearly Linear Sized Holographic Proofs. Proceedings of the Twenty Sixth Annual Symposium on the Theory of Computing, ACM, 1994.","DOI":"10.1145\/195058.195132"},{"key":"64_CR11","doi-asserted-by":"crossref","unstructured":"R. Raz, A parallel repetition theorem. Proceedings of the Twenty Seventh Annual Symposium on the Theory of Computing, ACM, 1995.","DOI":"10.1145\/225058.225181"},{"key":"64_CR12","series-title":"Lect Notes Comput Sci","volume-title":"Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems","author":"M. Sudan","year":"1992","unstructured":"M. Sudan, Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. Ph.D. Thesis, U.C. Berkeley, 1992. Also appears as ACM Distinguished Theses, Lecture Notes in Computer Science, no. 1001, Springer, 1996."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48523-6_64","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T03:11:26Z","timestamp":1642821086000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48523-6_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662242","9783540485230"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-48523-6_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"18 January 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}