{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:19:45Z","timestamp":1725517185256},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540852377"},{"type":"electronic","value":"9783540852384"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85238-4_18","type":"book-chapter","created":{"date-parts":[[2008,8,18]],"date-time":"2008-08-18T11:34:36Z","timestamp":1219059276000},"page":"229-240","source":"Crossref","is-referenced-by-count":0,"title":["Arthur and Merlin as Oracles"],"prefix":"10.1007","author":[{"given":"Venkatesan T.","family":"Chakaravarthy","sequence":"first","affiliation":[]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Alth\u00f6fer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications\u00a0199 (1994)","DOI":"10.1016\/0024-3795(94)90357-3"},{"issue":"2","key":"18_CR2","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. Journal of Computer and System Sciences\u00a036(2), 254\u2013276 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Cai, J.: $\\rm {S}_2^{\\it p} \\subseteq {ZPP}^{{NP}}$ . Journal of Computer and System Sciences\u00a073(1) (2007)","DOI":"10.1016\/j.jcss.2003.07.015"},{"key":"18_CR4","unstructured":"Chakaravarthy, V., Roy, S.: Finding irrefutable certificates for ${\\rm S}_2^p$ via Arthur and Merlin. In: STACS (2008)"},{"key":"18_CR5","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032916","volume-title":"Computational Complexity","author":"D. Du","year":"2000","unstructured":"Du, D., Ko, K.: Computational Complexity. John Wiley, Chichester (2000)"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Feigenbaum, J., Koller, D., Shor, P.: A game-theoretic classification of interactive complexity classes. In: CCC (1995)","DOI":"10.1109\/SCT.1995.514861"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Impagliazzo, R., Kabanets, V., Umans, C.: On the complexity of succinct zero-sum games. In: CCC (2005)","DOI":"10.1109\/CCC.2005.18"},{"issue":"5","key":"18_CR8","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A. Klivans","year":"2002","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses. SIAM Journal on Computing\u00a031(5), 1501\u20131526 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Lipton, R., Young, N.: Simple strategies for large zero-sum games with applications to complexity theory. In: STOC (1994)","DOI":"10.1145\/195058.195447"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Miltersen, P., Vinodchandran, N.: Derandomizing Arthur-Merlin games using hitting sets. In: FOCS (1999)","DOI":"10.1109\/SFFCS.1999.814579"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Neumann, J.: Zur theorie der gesellschaftspiel. Mathematische Annalen\u00a0100 (1928)","DOI":"10.1007\/BF01448847"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"J. Newman","year":"1991","unstructured":"Newman, J.: Private vs. common random bits in communication complexity. Information Processing Letters\u00a039, 67\u201371 (1991)","journal-title":"Information Processing Letters"},{"issue":"2","key":"18_CR13","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. Journal of Computer and System Sciences\u00a049(2), 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR14","volume-title":"Game Theory","author":"G. Owen","year":"1982","unstructured":"Owen, G.: Game Theory. Academic Press, London (1982)"},{"key":"18_CR15","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"4","key":"18_CR16","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/s00037-007-0218-9","volume":"15","author":"R. Shaltiel","year":"2007","unstructured":"Shaltiel, R., Umans, C.: Pseudorandomness for approximate counting and sampling. Computational Complexity\u00a015(4), 298\u2013341 (2007)","journal-title":"Computational Complexity"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: STOC (1983)","DOI":"10.1145\/800061.808762"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.: The complexity of approximate counting. In: STOC (1983)","DOI":"10.1145\/800061.808740"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85238-4_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T12:58:43Z","timestamp":1684501123000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85238-4_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540852377","9783540852384"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85238-4_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}