{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T14:10:05Z","timestamp":1737123005027,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540439967"},{"type":"electronic","value":"9783540456551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45655-4_4","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T11:37:01Z","timestamp":1179747421000},"page":"18-27","source":"Crossref","is-referenced-by-count":0,"title":["On Higher Arthur-Merlin Classes"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Charles","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samik","family":"Sengupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,8,29]]},"reference":[{"key":"4_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BFb0058034","volume-title":"Proc. 17th FST and TCS","author":"V. Arvind","year":"1997","unstructured":"V. Arvind and J. K\u00f6bler, On Pseudorandomness and Resource-Bounded Measure, Proc. 17th FST and TCS, Springer-Verlag, LNCS 1346, 235\u2013249, 1997."},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"V. Arvind and J. K\u00f6bler, Graph isomorphism is low for ZPP NP and other lowness results, STACS 2000.","DOI":"10.1007\/3-540-46541-3_36"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and hardness of approximation problems. Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra, Approximating clique is NP-complete., Proceedings of the 33rd IEEE Symposium on Foundations on Computer Science, 2\u201313, 1992.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"M. Agrawal and T. Thierauf, The Boolean isomorphism problem, Proc. 37th Annual Symposium on Foundations of Computer Science, 422\u2013430.","DOI":"10.1109\/SFCS.1996.548501"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"L. Babai, Trading group theory for randomness, STOC 17:421\u2013429(85).","DOI":"10.1145\/22145.22192"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"L. Babai and S. Moran, Arthur-Merlin Games: a randomized proof system, and a hierarchy of complexity classes, Journal of Computer and System Sciences, 36:254\u2013276, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, J. Gabarr\u00f3, Structural Complexity II, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. Boppana","year":"1987","unstructured":"R. Boppana, J. Hastad and S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, 25:127\u2013132, 1987.","journal-title":"Information Processing Letters"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"N. Bshouty, R. Cleve, S. Kannan and C. Tamon, Oracles and Queries that are sufficient for Exact Learning, Proceedings of the 17th Annual ACM conference on Computational Learning Theory, 130\u201319 (1994).","DOI":"10.1145\/180139.181067"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, S 2 P \u2286 ZPPNP, ECCC Tech-report TR-02-30, also to appear in FOCS 2001.","DOI":"10.1109\/SFCS.2001.959938"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, S. Micali and C. Rackoff, The Knowledge Complexity of Interactive Proofs, Proc. 17th ACM Symp. om Computing, Providence, RI, 1985, pp. 291\u2013304.","DOI":"10.1145\/22145.22178"},{"key":"4_CR13","first-page":"59","volume":"18","author":"S. Goldwasser","year":"1986","unstructured":"S. Goldwasser and M. Sipser, Private coins versus public coins in interactive proof systems, STOC 18:59\u201368(1986).","journal-title":"STOC"},{"key":"4_CR14","unstructured":"O. Goldreich and D. Zuckerman, Another Proof that BPP \u2286 PH (and more), ECCC, TR97-045, October 1997."},{"key":"4_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/3-540-60084-1_74","volume-title":"ICALP","author":"J. K\u00f6bler","year":"1995","unstructured":"J. K\u00f6bler and O. Watanabe, New collapse consequences of NP having small circuits ICALP, LNCS 944:196\u2013207(1995)."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"C. Lund, L. Fortnow, H. Karloff and N. Nisan, Algebraic Methods for Interactive Proof Systems, Journal of the ACM, 39(4):859\u2013868, October 1992.","DOI":"10.1145\/146585.146605"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"A. Shamir, IP = PSPACE, Journal of the ACM, 39(4):869\u2013877, October 1992.","DOI":"10.1145\/146585.146609"},{"issue":"5","key":"4_CR18","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda, PP is as hard as polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865\u2013877, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1142\/S0129054193000195","volume":"4","author":"H. Vollmer","year":"1993","unstructured":"H. Vollmer and K. Wagner, The complexity of finding middle elements. International Journal of Foundations of Computer Science, 4:293\u2013307, 1993.","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"1","key":"4_CR20","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"O. Watanabe","year":"1992","unstructured":"O. Watanabe and S. Toda, Polynomial time 1-Turing reductions from #PH to #P. Theoritical Computer Science, 100(1):205\u2013221, 1992.","journal-title":"Theoritical Computer Science"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0019-9958(86)80044-4","volume":"69","author":"S. Zachos","year":"1986","unstructured":"S. Zachos and H. Heller, A Decisive characterization of BPP, Information and Control, 69:125\u2013135(1986).","journal-title":"Information and Control"},{"key":"4_CR22","series-title":"Lect Notes Comput Sci","first-page":"449","volume-title":"FSTTCS","author":"S. Zachos","year":"1987","unstructured":"S. Zachos and M. F\u00fcrer, Probabilistic quantifiers vs Distrustful adversaries, FSTTCS 1987, LNCS-287:449\u2013455."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45655-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T14:32:35Z","timestamp":1737037955000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45655-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540439967","9783540456551"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-45655-4_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}