{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T14:12:44Z","timestamp":1791295964756,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540186250","type":"print"},{"value":"9783540480334","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18625-5_67","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T14:40:50Z","timestamp":1330180850000},"page":"443-455","source":"Crossref","is-referenced-by-count":17,"title":["Probabilistic quantifiers vs. distrustful adversaries"],"prefix":"10.1007","author":[{"given":"Stathis","family":"Zachos","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Furer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"BABAI, L., Trading Group Theory for Randomness, 17th STOC, (1985), 421\u2013429.","DOI":"10.1145\/22145.22192"},{"key":"31_CR2","first-page":"27","volume":"12","author":"L. Babai","year":"1982","unstructured":"BABAI, L., and ERDOS, P., Representation of Group Elements as as short Products, in: Theory and Practice of Combinatorics (A. Rosa et al. eds.), Annals of Discr. Math. 12, (1982), 27\u201330.","journal-title":"Annals of Discr. Math."},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. H. Bennett","year":"1981","unstructured":"BENNETT, C.H., and GILL, J., Relative to a Random Oracle A, P A \u2260 NP A \u2260 co \u2212NP A , SIAM J. Comput 10, (1981), 96\u2013113.","journal-title":"SIAM J. Comput"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. B. Boppana","year":"1986","unstructured":"BOPPANA, R.B., HASTAD, J., and ZACHOS, S., Does co-NP have Short Interactive Proofs?, (1986), IPL 25, (1987), 127\u2013132.","journal-title":"IPL"},{"key":"31_CR5","first-page":"229","volume":"25","author":"L.. Babai","year":"1984","unstructured":"BABAI, L.., and SZEMEREDI, E., On the Complexity of Matrix Group Problems I, FOCS 25, (1984), 229\u2013240.","journal-title":"FOCS"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"FURST, M.L., HOPCROFT, J., and LUKS, E.M., Polynomial-time Algorithms for Permutation Groups, 21st FOCS, (1980), 36\u201341.","DOI":"10.1109\/SFCS.1980.34"},{"key":"31_CR7","unstructured":"FORTNOW, L., and SIPSER, M., Private Communication."},{"key":"31_CR8","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 J. of Computing 6, (1977), 675\u2013695.","journal-title":"SIAM J. of Computing"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"GALIL, Z., HABER, S., and YUNG, M., A Private Interactive Test of a Boolean Predicate and Minimum \u2014 Knowledge Public \u2014 Key Cryptosystems, 26th FOCS, (1985), 360\u2013371.","DOI":"10.1109\/SFCS.1985.1"},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"GOLDWASSER, S., MICALI, S., and RACKOFF, C., The Knowledge Complexity of Interactive Proof Systems, 17th STOC, (1985), 291\u2013304.","DOI":"10.1145\/22145.22178"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"GOLDWASSER, S., and SIPSER, M., Private Coins versus Public Coins in Interactive Proof Systems, 18th STOC, (1986), 59\u201368.","DOI":"10.1145\/12130.12137"},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"HINMAN, P. and ZACHOS, S., Probabilistic Machines, Oracles and Quantifiers, Proceedings of the Oberwolfach Recursion-theoretic Week, Lecture Notes in Mathematics 1141, Springer-Verlag, (1984), 159\u2013192.","DOI":"10.1007\/BFb0076220"},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"PAPADIMITRIOU, C.H., Games against Nature, 24th FOCS, (1983), 446\u2013450.","DOI":"10.1109\/SFCS.1983.20"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"PAPADIMITRIOU, C.H., and YANNAKAKIS, M., The Complexity of Facets (and some facets of complexity), 14th STOC, (1982), 255\u2013260.","DOI":"10.1145\/800070.802199"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1976","unstructured":"STOCKMEYER, L.J., The Polynomial-Time Hierarchy, TCS 3, (1976), 1\u201322.","journal-title":"TCS"},{"key":"31_CR16","unstructured":"SCHOENING, U., Graph Isomorphism is in the Low Hierarchy, (1986), submitted for publication."},{"key":"31_CR17","doi-asserted-by":"crossref","unstructured":"SIMS, C.C., Some Group Theoretic Algorithms, Lect. Notes in Math. 697, Springer-Verlag, (1978), 108\u2013124.","DOI":"10.1007\/BFb0103126"},{"key":"31_CR18","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1977","unstructured":"SOLOVAY, R., and STRASSEN, V., A fast Monte-Carlo test for primality, SIAM J. of Computing 6, (1977) 84\u201385.","journal-title":"SIAM J. of Computing"},{"key":"31_CR19","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"WRATHALL, C., Complete Sets and the Polynomial-Time Hierarchy, TCS 3, (1976), 23\u201333.","journal-title":"TCS"},{"key":"31_CR20","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0019-9958(82)80019-3","volume":"54","author":"S. Zachos","year":"1982","unstructured":"ZACHOS, S., Robustness of Probabilistic Computational Complexity Classes under Definional Perturbations, Information and Control, (1982), 54, 143\u2013154.","journal-title":"Information and Control"},{"key":"31_CR21","unstructured":"ZACHOS, S., and HELLER, H., On BPP, TM-252, LCS, MIT, (1983)."},{"key":"31_CR22","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0019-9958(86)80044-4","volume":"69","author":"S. Zachos","year":"1986","unstructured":"ZACHOS, S., and HELLER, H., A Decisive Characterization of BPP, Information and Control, (1986), 69, 125\u2013135.","journal-title":"Information and Control"},{"key":"31_CR23","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/3-540-16486-3_112","volume":"223","author":"S. Zachos","year":"1986","unstructured":"ZACHOS, S., Probabilistic Quantifiers, Adversaries, and Complexity Classes: An Overview, Proceedings of Structure in Complexity Theory Conference, Lecture Notes in Computer Science, 223, (1986), 383\u2013400.","journal-title":"Lecture Notes in Computer Science"},{"key":"31_CR24","unstructured":"ZACHOS, S., Probabilistic Oracles are less Powerfull than Nondeterministic Oracles, submitted for publication, (1986)."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18625-5_67.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:15:18Z","timestamp":1605626118000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18625-5_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540186250","9783540480334"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-18625-5_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987]]}}}