{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:48:30Z","timestamp":1725558510186},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540406716"},{"type":"electronic","value":"9783540451389"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45138-9_19","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T18:41:48Z","timestamp":1277232108000},"page":"249-258","source":"Crossref","is-referenced-by-count":2,"title":["Error-Bounded Probabilistic Computations between MA and AM"],"prefix":"10.1007","author":[{"given":"Elmar","family":"B\u00f6hler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Gla\u00dfer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Meister","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","first-page":"745","volume-title":"Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms","author":"J. Aspnes","year":"2001","unstructured":"Aspnes, J., Fischer, D.F., Fischer, M.J., Kao, M.Y., Kumar, A.: Towards understanding the predictability of stock markets from the perspective of computational complexity. In: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pp. 745\u2013754. ACM Press, New York (2001)"},{"key":"19_CR2","first-page":"421","volume-title":"Proceedings 17th Symposium on Theory of Computing","author":"L. Babai","year":"1985","unstructured":"Babai, L.: Trading group theory for randomness. In: Proceedings 17th Symposium on Theory of Computing, pp. 421\u2013429. ACM Press, New York (1985)"},{"key":"19_CR3","unstructured":"B\u00f6hler, E., Gla\u00dfer, C., Meister, D.: Error-bounded probabilistic computations between MA and AM. Technical Report 299, Julius-Maximilians-Universit\u00e4t W\u00fcrzburg (2002), Available at \n                    \n                      http:\/\/www.informatik.uni-wuerzburg.de\/reports\/tr.html"},{"issue":"2","key":"19_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R.B. Boppana","year":"1987","unstructured":"Boppana, R.B., H\u00e5stad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters\u00a025(2), 127\u2013132 (1987)","journal-title":"Information Processing Letters"},{"key":"19_CR5","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, 254\u2013276 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0304-3975(79)90043-4","volume":"8","author":"T.P. Baker","year":"1979","unstructured":"Baker, T.P., Selman, A.L.: A second step towards the polynomial hierarchy. Theoretical Computer Science\u00a08, 177\u2013187 (1979)","journal-title":"Theoretical Computer Science"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"de Leeuw, K., Moore, E.F., Shannon, C.E., Shapiro, N.: Computability by probabilistic machines. In: Shannon, C.E. (ed.) Automata Studies, Annals of Mathematical Studies, Rhode Island, vol.\u00a034, pp. 183\u2013198 (1956)","DOI":"10.1515\/9781400882618-010"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. Fenner","year":"1994","unstructured":"Fenner, S., Fortnow, L., Kurtz, S.: Gap-definable counting classes. Journal of Computer and System Sciences\u00a048, 116\u2013148 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR9","unstructured":"Gill, J.: Probabilistic Turing Machines and Complexity of Computations. PhD thesis, University of California Berkeley (1972)"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic turing machines. SIAM Journal on Computing\u00a06, 675\u2013695 (1977)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"19_CR11","first-page":"691","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Widgerson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the Association for Computing Machinery\u00a038(1), 691\u2013729 (1991)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"19_CR12","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1006\/jcss.1995.1032","volume":"50","author":"S. Gupta","year":"1995","unstructured":"Gupta, S.: Closure properties and witness reductions. Journal of Computer and System Sciences\u00a050, 412\u2013432 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","volume":"58","author":"J. Hartmanis","year":"1988","unstructured":"Hartmanis, J., Hemachandra, L.A.: Complexity classes without machines: On complete languages for UP. Theoretical Computer Science\u00a058, 129\u2013142 (1988)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"19_CR14","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/S0097539792240467","volume":"26","author":"Y. Han","year":"1997","unstructured":"Han, Y., Hemaspaandra, L.A., Thierauf, T.: Threshold computation and cryptographic security. SIAM Journal on Computing\u00a026(1), 59\u201378 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR15","first-page":"191","volume":"28","author":"R. Karp","year":"1982","unstructured":"Karp, R., Lipton, R.: Turing machines that take advice. L\u2019enseignement math\u00e9matique\u00a028, 191\u2013209 (1982)","journal-title":"L\u2019enseignement math\u00e9matique"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/0890-5401(89)90022-9","volume":"80","author":"M. Santha","year":"1989","unstructured":"Santha, M.: Relativized Arthur-Merlin versus Merlin-Arthur games. Information and Computation\u00a080, 44\u201349 (1989)","journal-title":"Information and Computation"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences\u00a037, 312\u2013323 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/0022-0000(89)90020-2","volume":"39","author":"U. Sch\u00f6ning","year":"1989","unstructured":"Sch\u00f6ning, U.: Probabilistic complexity classes and lowness. Journal of Computer and System Sciences\u00a039, 84\u2013100 (1989)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR19","unstructured":"Simon, J.: On Some Central Problems in Computational Complexity. PhD thesis, Cornell University (1975)"},{"key":"19_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/BFb0012797","volume-title":"Automata, Languages, and Programming","author":"M. Sipser","year":"1982","unstructured":"Sipser, M.: On relativization and the existence of complete sets. In: Nielsen, M., Schmidt, E.M. (eds.) ICALP 1982. LNCS, vol.\u00a0140, pp. 523\u2013531. Springer, Heidelberg (1982)"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: Proceedings of the 15th Symposium on Theory of Computing, pp. 330\u2013335 (1983)","DOI":"10.1145\/800061.808762"},{"key":"19_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.: The polynomial-time hierarchy. Theoretical Computer Science\u00a03, 1\u201322 (1977)","journal-title":"Theoretical Computer Science"},{"key":"19_CR23","unstructured":"Vazirani, U.: Randomness, Adversaries and Computation. PhD thesis, University of California Berkeley (1986)"},{"key":"19_CR24","first-page":"138","volume-title":"Proceedings 7th Structure in Complexity Theory","author":"N.K. Vereshchagin","year":"1992","unstructured":"Vereshchagin, N.K.: On the power of PP. In: Proceedings 7th Structure in Complexity Theory, pp. 138\u2013143. IEEE Computer Society Press, Los Alamitos (1992)"},{"key":"19_CR25","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"Wrathall, C.: Complete sets and the polynomial-time hierarchy. Theoretical Computer Science\u00a03, 23\u201333 (1977)","journal-title":"Theoretical Computer Science"},{"key":"19_CR26","first-page":"1","volume-title":"Proceedings 26th Foundations of Computer Science","author":"A.C.C. Yao","year":"1985","unstructured":"Yao, A.C.C.: Separating the polynomial-time hierarchy by oracles. In: Proceedings 26th Foundations of Computer Science, pp. 1\u201310. IEEE Computer Society Press, Los Alamitos (1985)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45138-9_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,14]],"date-time":"2019-03-14T21:44:47Z","timestamp":1552599887000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45138-9_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540406716","9783540451389"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45138-9_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}