{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:08Z","timestamp":1742617208851,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_9","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:48Z","timestamp":1330290288000},"page":"99-110","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Solvable black-box group problems are low for PP"],"prefix":"10.1007","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/0405008","volume":"5","author":"L. Babai","year":"1992","unstructured":"L. Babai. Bounded round interactive proofs in finite groups. SIAM Journal of Discrete Mathematics, 5: 88\u2013111, 1992.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"L. Babai. Trading group theory for randomness. 17th ACM Symp. Theory of Computing, 421\u2013429, 1985.","DOI":"10.1145\/22145.22192"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1006\/jcss.1995.1024","volume":"50","author":"L. Babai","year":"1995","unstructured":"L. Babai, G. Cooperman, L. Finkelstein, E. Luks and \u00c1. Seress. Fast Monte Carlo algorithms for permutation groups. In Journal of Computer and System Sciences,50: 296\u2013308, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR4","doi-asserted-by":"crossref","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":"9_CR5","doi-asserted-by":"crossref","unstructured":"L. Babai, E. Luks and \u00c1. Seress. Fast management of permutation groups. Proc. 28th IEEE Symposium on Foundations of Computer Science, 272\u2013282, 1988.","DOI":"10.1109\/SFCS.1988.21943"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"L. Babai and M. Szemer\u00e9di. On the complexity of matrix group problems I. Proc. 25th IEEE Symposium on Foundations of Computer Science, 229\u2013240, 1984.","DOI":"10.1109\/SFCS.1984.715919"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"R. Beals and L. Babai. Las Vegas algorithms for matrix groups. Proc. 25th ACM Symposium on Theory of Computing, pp. 427\u2013436, 1993.","DOI":"10.1109\/SFCS.1993.366844"},{"key":"9_CR8","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 coNP have short interactive proofs? Information Processing Letters, 25: 127\u2013132, 1987.","journal-title":"Information Processing Letters"},{"key":"9_CR9","unstructured":"W. Burnside. Theory of Groups of Finite Order, Dover Publications, INC, 1955."},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"G. Cooperman and L. Finkelstein. Combinatorial tools for computational group theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 11, 1993.","DOI":"10.1090\/dimacs\/011\/05"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow, S. Kurtz. Gap-definable counting classes. Proc. 6th Structure in Complexity Theory Conference, 30\u201342, 1991.","DOI":"10.1109\/SCT.1991.160241"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"M. Fellows and N. Koblitz. Self-witnessing polynomial time complexity and prime factorization. Proc. 6th Structure in Complexity Theory Conference, 107\u2013110, 1992.","DOI":"10.1109\/SCT.1992.215385"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"M. Furst, J. E. Hopcroft and E. Luks. Polynomial time algorithms for permutation groups. Proc. 21st IEEE Symposium of Foundations of Computer Science, 36\u201345, 1980.","DOI":"10.1109\/SFCS.1980.34"},{"key":"9_CR14","volume-title":"The Theory of Groups","author":"M. Hall","year":"1959","unstructured":"M. Hall. The Theory of Groups. Macmillan, New York, 1959."},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"C. Hoffmann. Group-Theoretic Algorithms and Graph Isomorphism. Lecture Notes in Computer Science #136, Springer Verlag, 1982.","DOI":"10.1007\/3-540-11493-9"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01200427","volume":"2","author":"J. K\u00f6bler","year":"1992","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, J. Tor\u00e1n. Graph isomorphism is low for PP. Journal of Computational Complexity, 2: 301\u2013310, 1992.","journal-title":"Journal of Computational Complexity"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"E. M. Luks. Computing in solvable matrix groups. Proc. 33rd IEEE Symposium on Foundations of Computer Science, 111\u2013120, 1992.","DOI":"10.1109\/SFCS.1992.267813"},{"key":"9_CR18","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Sch\u00f6ning","year":"1988","unstructured":"U. Sch\u00f6ning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37: 312\u2013323, 1988.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:52Z","timestamp":1742598652000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_9"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"7 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}