{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T18:25:34Z","timestamp":1773253534085,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540369257","type":"print"},{"value":"9783540369264","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11809678_15","type":"book-chapter","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T09:41:33Z","timestamp":1155634893000},"page":"126-135","source":"Crossref","is-referenced-by-count":4,"title":["The Complexity of Black-Box Ring Problems"],"prefix":"10.1007","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bireswar","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Partha","family":"Mukhopadhyay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"15_CR1","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M. Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Annals of Mathematics\u00a0160(2), 781\u2013793 (2004)","journal-title":"Annals of Mathematics"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-31856-9_1","volume-title":"STACS 2005","author":"M. Agrawal","year":"2005","unstructured":"Agrawal, M., Saxena, N.: Automorphisms of Finite Rings and Applications to Complexity of Problems. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 1\u201317. Springer, Heidelberg (2005)"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L.: Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups. In: STOC 1991, pp. 164\u2013174 (1991)","DOI":"10.1145\/103418.103440"},{"issue":"1","key":"15_CR4","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/0405008","volume":"5","author":"L. Babai","year":"1992","unstructured":"Babai, L.: Bounded Round Interactive Proofs in Finite Groups. SIAM J. Discrete Math.\u00a05(1), 88\u2013111 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR5","volume-title":"ETACS Monographs on Theoretical Computer Science","author":"J.L. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, D.: Structural Complexity I. ETACS Monographs on Theoretical Computer Science. Springer, Heidelberg (1988) (I)"},{"key":"15_CR6","volume-title":"ETACS Monographs on Theoretical Computer Science","author":"J.L. Balc\u00e1zar","year":"1990","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, D.: Structural Complexity II. ETACS Monographs on Theoretical Computer Science. Springer, Heidelberg (1990) (II)"},{"issue":"2","key":"15_CR7","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 Comput. Syst. Sciences\u00a036(2), 254\u2013276 (1988)","journal-title":"Journal Comput. Syst. Sciences"},{"key":"15_CR8","volume-title":"Finite Rings with Identity","author":"B.R. McDonald","year":"1974","unstructured":"McDonald, B.R.: Finite Rings with Identity. Marcel Dekker Inc., New York (1974)"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Babai, L., Szemer\u00e9di, E.: On the complexity of matrix group problems I. In: Proc. 25th IEEE Sympos. on the Foundation of Computer Science, pp. 229\u2013240 (1984)","DOI":"10.1109\/SFCS.1984.715919"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Vazirani, U., Bernstein, E.: Quantum Complexity Theory. Special issue on Quantum Computation of the Siam Journal of Computing (October 1997)","DOI":"10.1137\/S0097539796300921"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Cheung, K.K.H., Mosca, M.: Decomposing Finite Abelian Groups. Los Alamos Preprint Archive, quant-ph\/0101004 (2001)","DOI":"10.26421\/QIC1.3-2"},{"key":"15_CR12","unstructured":"Eberly, W.: Computations for algebras and group representations, PhD thesis. University of Toronto (1989)"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Friedl, K., R\u00f3nyai, L.: Polynomial time solutions for some problems in computational algebra. In: Proc. 17th Ann. Symp. Theory of Computing, pp. 153\u2013162 (1985)","DOI":"10.1145\/22145.22162"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Kayal, N., Saxena, N.: On the Ring Isomorphism and Automorphism Problems. In: IEEE Conference on Computational Complexity, pp. 2\u201312 (2005)","DOI":"10.1109\/CCC.2005.22"},{"issue":"2","key":"15_CR15","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1090\/S0273-0979-1992-00284-7","volume":"26","author":"H.W. Lenstra Jr.","year":"1992","unstructured":"Lenstra Jr., H.W.: Algorithms in algebraic number theory. Bulletin of the AMS\u00a026(2), 211\u2013244 (1992)","journal-title":"Bulletin of the AMS"},{"issue":"5","key":"15_CR16","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P. Shor","year":"1997","unstructured":"Shor, P.: Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing\u00a026(5), 1484\u20131509 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Sanders, T., Shokrollahi, M.A.: Deciding properties of polynomials without factoring. In: Proc. 38th IEEE Foundations of Computer Science, pp. 46\u201355 (1997)","DOI":"10.1109\/SFCS.1997.646092"},{"key":"15_CR18","volume-title":"Modern Computer Algebra","author":"J.v.z. Gathen","year":"2003","unstructured":"Gathen, J.v.z., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003)","edition":"2"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11809678_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,31]],"date-time":"2021-07-31T08:15:11Z","timestamp":1627719311000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11809678_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540369257","9783540369264"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11809678_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}