{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:35:19Z","timestamp":1764783319512,"version":"3.38.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,8,5]],"date-time":"2011-08-05T00:00:00Z","timestamp":1312502400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00037-011-0015-3","type":"journal-article","created":{"date-parts":[[2011,8,4]],"date-time":"2011-08-04T14:07:54Z","timestamp":1312466874000},"page":"505-558","source":"Crossref","is-referenced-by-count":3,"title":["Arthur and Merlin as Oracles"],"prefix":"10.1007","volume":"20","author":[{"given":"Venkatesan T.","family":"Chakaravarthy","sequence":"first","affiliation":[]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,8,5]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/0024-3795(94)90357-3","volume":"199","author":"I. Alth\u00f6fer","year":"1994","unstructured":"Alth\u00f6fer I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications 199, 339\u2013355 (1994)","journal-title":"Linear Algebra and its Applications"},{"issue":"1\u20132","key":"15_CR2","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0304-3975(99)00164-4","volume":"255","author":"V. Arvind","year":"2001","unstructured":"Arvind V., K\u00f6bler J.: On pseudorandomness and resource-bounded measure. Theoretical Computer Science 255(1\u20132), 205\u2013221 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"15_CR3","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0304-3975(95)91133-B","volume":"137","author":"V. Arvind","year":"1995","unstructured":"Arvind V., K\u00f6bler J., Sch\u00f6ning U., Schuler R.: If NP has polynomial-size circuits, then MA=AM. Theoretical Computer Science 137(2), 279\u2013282 (1995)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"15_CR4","doi-asserted-by":"crossref","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 36(2), 254\u2013276 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"15_CR5","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N. Bshouty","year":"1996","unstructured":"Bshouty N., Cleve R., Gavald\u00e0 R., Kannan S., Tamon C.: Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences 52(3), 421\u2013433 (1996)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"15_CR6","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jcss.2003.07.015","volume":"73","author":"J. Cai","year":"2007","unstructured":"Cai J.: $${{\\rm S}_2^p \\subseteq {\\rm ZPP}^{{\\rm NP}}}$$ . Journal of Computer and System Sciences 73(1), 25\u201335 (2007)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"15_CR7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0020-0190(96)00016-6","volume":"57","author":"R. Canetti","year":"1996","unstructured":"Canetti R.: More on BPP and the polynomial-time hierarchy. Information Processing Letters 57(5), 237\u2013241 (1996)","journal-title":"Information Processing Letters"},{"key":"15_CR8","unstructured":"V. Chakaravarthy and S. Roy, Oblivious symmetric alternation. In Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, vol. 3884 of Lecture Notes in Computer Science, 2006, 230\u2013241."},{"key":"15_CR9","unstructured":"V. Chakaravarthy and S. Roy, Finding irrefutable certificates for $${{\\rm S}_2^p}$$ via Arthur and Merlin. In Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, vol. 1 of LIPIcs. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Germany, 2008a, 157\u2013168."},{"key":"15_CR10","unstructured":"V. Chakaravarthy and S. Roy, Arthur and Merlin as oracles. In Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, vol. 5162 of Lecture Notes in Computer Science, 2008b, 229\u2013240."},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"D. Du and K. Ko, Computational Complexity. John Wiley and sons, 2000.","DOI":"10.1002\/9781118032916"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum, D. Koller, and P. Shor, A game-theoretic classification of interactive complexity classes. In Proceedings of the 10th Annual IEEE Conference on Computational Complexity, 1995, 227\u2013237.","DOI":"10.1109\/SCT.1995.514861"},{"issue":"3","key":"15_CR13","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s00037-008-0252-2","volume":"17","author":"L. Fortnow","year":"2008","unstructured":"Fortnow L., Impagliazzo R., Kabanets V., Umans C.: On the complexity of succinct zero-sum games. Computational Complexity 17(3), 353\u2013376 (2008a)","journal-title":"Computational Complexity"},{"issue":"3","key":"15_CR14","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/j.jcss.2007.06.017","volume":"74","author":"L. Fortnow","year":"2008","unstructured":"Fortnow L., Pavan A., Sengupta S.: Proving SAT does not have small circuits with an application to the two queries problem. Journal of Computer and System Sciences 74(3), 358\u2013363 (2008)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR15","unstructured":"O. Goldreich and A. Wigderson, Improved derandomization of BPP using a hitting set generator. In RANDOM-APPROX, vol. 1671 of Lecture Notes in Computer Science, 1999, 131\u2013137."},{"key":"15_CR16","unstructured":"O. Goldreich and D. Zuckerman, Another proof that $${{\\rm BPP} \\subseteq {\\rm PH}}$$ (and more). Technical Report TR97\u2013045, ECCC, 1997."},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and A. Wigderson., P=BPP unless E has subexponential circuits: Derandomizing the XOR lemma. In Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, 220\u2013229.","DOI":"10.1145\/258533.258590"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton, Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, 302\u2013309.","DOI":"10.1145\/800141.804678"},{"issue":"5","key":"15_CR19","doi-asserted-by":"crossref","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 31(5), 1501\u20131526 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"15_CR20","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1137\/S0097539795296206","volume":"28","author":"J. K\u00f6bler","year":"1998","unstructured":"K\u00f6bler J., Watanabe O.: New collapse consequences of NP having small circuits. SIAM Journal on Computing 28(1), 311\u2013324 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"R. Lipton and N. Young, Simple strategies for large zero-sum games with applications to complexity theory. In Proceedings of the 26th ACM Symposium on Theory of Computing, 1994, 734\u2013740.","DOI":"10.1145\/195058.195447"},{"issue":"3","key":"15_CR22","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/s00037-005-0197-7","volume":"14","author":"P. Miltersen","year":"2005","unstructured":"Miltersen P., Vinodchandran N.: Derandomizing Arthur-Merlin games using hitting sets. Computational Complexity 14(3), 256\u2013279 (2005)","journal-title":"Computational Complexity"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"J. Neumann, Zur theorie der gesellschaftspiel. Mathematische Annalen 100(1928).","DOI":"10.1007\/BF01448847"},{"key":"15_CR24","doi-asserted-by":"crossref","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 39, 67\u201371 (1991)","journal-title":"Information Processing Letters"},{"issue":"2","key":"15_CR25","doi-asserted-by":"crossref","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 49(2), 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR26","unstructured":"G. Owen, Game Theory. Academic Press, 1982."},{"key":"15_CR27","unstructured":"C. Papadimitriou, Computational Complexity. Addison-Wesley, 1994."},{"issue":"2","key":"15_CR28","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/s000370050007","volume":"7","author":"A. Russell","year":"1998","unstructured":"Russell A., Sundaram R.: Symmetric alternation captures BPP. Computational Complexity 7(2), 152\u2013162 (1998)","journal-title":"Computational Complexity"},{"issue":"4","key":"15_CR29","doi-asserted-by":"crossref","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 15(4), 298\u2013341 (2007)","journal-title":"Computational Complexity"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"M. Sipser, A complexity theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on Theory of Computing, 1983, 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"15_CR31","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer, The complexity of approximate counting. In Proceedings of the 15th ACM Symposium on Theory of Computing, 1983, 118\u2013126.","DOI":"10.1145\/800061.808740"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0015-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0015-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0015-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T05:20:09Z","timestamp":1741411209000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0015-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,5]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["15"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0015-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2011,8,5]]}}}