{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:48Z","timestamp":1725663648152},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_52","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:16:49Z","timestamp":1330255009000},"page":"525-534","source":"Crossref","is-referenced-by-count":5,"title":["Transparent (holographic) proofs"],"prefix":"10.1007","author":[{"given":"L\u00e1szl\u00f3","family":"Babai","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"52_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. In:Proc. 33rd IEEE FOCS (1992), pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"52_CR2","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs. In: Proc. 33rd IEEE FOCS (1992), pp. 2\u201313."},{"key":"52_CR3","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.: Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity 1 (1991) 3\u201340.","journal-title":"Computational Complexity"},{"key":"52_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proc. 23rd ACM STOC (1991), pp. 21\u201331.","DOI":"10.1145\/103418.103428"},{"key":"52_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: How to remove the intractability assumptions. In: Proc. 20th ACM STOC (1988), pp. 113\u2013131.","DOI":"10.1145\/62212.62223"},{"key":"52_CR6","unstructured":"Blum, A., Jiang, T., Li, M., Tromp. J., Yannakakis, M.: Linear approximation of shortest superstrings. In: Proc. 23rd ACM STOC (1991), pp. 328\u2013336."},{"key":"52_CR7","doi-asserted-by":"crossref","unstructured":"Blum, M., Kannan, S.: Designing Programs that Check Their Work. In: Proc. 21st ACM STOC (1989), pp. 86\u201397.","DOI":"10.1145\/73007.73015"},{"key":"52_CR8","doi-asserted-by":"crossref","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with Applications to Numerical Problems. In: Proc. 22nd ACM Symp. on Theory of Computing (1990), pp. 73\u201383.","DOI":"10.1145\/100216.100225"},{"key":"52_CR9","unstructured":"Gonick, Larry: Proof Positive? Discover Magazine, \u201cScience classics\u201d section, August 1992, pp. 2\u201327."},{"key":"52_CR10","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Approximating clique is almost NP-complete. In: Proc. 32nd IEEE FOCS (1991) 2\u201312."},{"key":"52_CR11","unstructured":"Feige, U., Lov\u00e1sz, L.: Two-prover one-round proof systems: their power and their problems. In: Proc. 24th ACM STOC (1992), pp. 733\u2013744."},{"key":"52_CR12","unstructured":"Fortnow, L.: private communication, 1992"},{"key":"52_CR13","unstructured":"Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols. In: Proc. 3rd Structure in Complexity Theory Conf. (1988), pp. 156\u2013161."},{"key":"52_CR14","volume-title":"A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., Johnson, D. S.: Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, New York, 1979."},{"key":"52_CR15","unstructured":"Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., Wigderson, A.: Selftesting\/correcting for polynomials and for approximate functions. In: Proc. 23rd ACM STOC (1991) pp. 32\u201342."},{"key":"52_CR16","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Zuckerman, D., How to recycle random bits. In: Proc. 30th IEEE FOCS (1989), pp. 248\u2013253.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"52_CR17","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1016\/0196-6774(92)90052-E","volume":"13","author":"D. S. Johnson","year":"1992","unstructured":"Johnson, D. S.: The NP-Completeness Column: An Ongoing Guide. J. of Algorithms 13 (1992), 502\u2013524.","journal-title":"J. of Algorithms"},{"key":"52_CR18","volume-title":"Ph.D. Thesis","author":"V. Kann","year":"1992","unstructured":"Kann, Viggo: On the approximability of NP-complete optimization problems. Ph.D. Thesis. Royal Institute of Technology, Stockholm, Sweden. May 1992."},{"key":"52_CR19","doi-asserted-by":"crossref","unstructured":"Karger, D., Motwani, R., Ramkumar, G. D. S.: On approximating the longest path in a graph. Manuscript, 1992.","DOI":"10.1007\/3-540-57155-8_267"},{"key":"52_CR20","unstructured":"Lapidot, D., Shamir, A.: Fully Parallelized Multi Prover Protocols for NEXPTIME. In: Proc. 32nd IEEE FOCS, 1991, pp. 13\u201318."},{"key":"52_CR21","unstructured":"Lund, Carsten: Efficient probabilistically checkable proofs. Manuscript, November 1992."},{"key":"52_CR22","doi-asserted-by":"crossref","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic Methods for Interactive Proof Systems. In: Proc. 31th IEEE FOCS (1990), pp. 2\u201310.","DOI":"10.1109\/FSCS.1990.89518"},{"key":"52_CR23","doi-asserted-by":"crossref","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. AT& T Technical Memorandum, 1992. Submitted to STOC'93.","DOI":"10.1145\/167088.167172"},{"key":"52_CR24","unstructured":"Kolata, Gina: New Short Cut Found for Long Math Proofs. The New York Times, April 7, 1992, Science Times section, p. B5."},{"key":"52_CR25","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. In: Proc. 20th ACM STOC (1988), pp. 510\u2013513.","DOI":"10.1145\/62212.62233"},{"key":"52_CR26","unstructured":"Phillips, S., Safra, S.: PCP and tighter bounds for approximating MAX \u2014 SNP. Manuscript, Stanford University, April 1992."},{"key":"52_CR27","volume-title":"Ph.D. Thesis","author":"R. Rubinfeld","year":"1990","unstructured":"Rubinfeld, R.: A Mathematical Theory of Self-Checking, Self-Testing and Self-Correcting Programs. Ph.D. Thesis, Computer Science Dept., U.C. Berkeley (1990)"},{"key":"52_CR28","unstructured":"Rubinfeld, R., Sudan, M.: Testing polynomial functions efficiently and over rational domains. In:Proc. 3rd ACM-SIAM SODA (1992) 23\u201332"},{"key":"52_CR29","doi-asserted-by":"crossref","first-page":"382","DOI":"10.2307\/3976271","volume":"141","author":"I. Peterson","year":"1992","unstructured":"Peterson, Ivars: Holographic proofs: keeping computers and mathematicians honest. Science News, vol. 141 (1992), 382\u2013383.","journal-title":"Science News"},{"key":"52_CR30","unstructured":"Cipra, Barry A.: Theoretical Computer Scientists Develop Transparent Proof Technique. SIAM News, vol. 25, No. 3, May 1992."},{"key":"52_CR31","unstructured":"Sudan, Madhu: Efficient checking of polynomials and proofs and the hardness of approximation problems. Ph.D. Thesis. U.C. Berkeley. October 1992."}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_52.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:04:26Z","timestamp":1605647066000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}