{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:50:35Z","timestamp":1743007835255,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031521126"},{"type":"electronic","value":"9783031521133"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-52113-3_27","type":"book-chapter","created":{"date-parts":[[2024,2,7]],"date-time":"2024-02-07T00:02:50Z","timestamp":1707264170000},"page":"383-397","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of\u00a0Spherical Equations in\u00a0Finite Groups"],"prefix":"10.1007","author":[{"given":"Caroline","family":"Mattes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9042-7857","authenticated-orcid":false,"given":"Alexander","family":"Ushakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7645-5867","authenticated-orcid":false,"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,7]]},"reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1090\/S0025-5718-1987-0866095-8","volume":"48","author":"LM Adleman","year":"1987","unstructured":"Adleman, L.M., Estes, D., McCurley, K.S.: Solving bivariate quadratic congruences in random polynomial time. Math. Comput. 48, 17\u201328 (1987)","journal-title":"Math. Comput."},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: Primes is in P. Ann. Math. 160, 781\u2013793 (2004)","DOI":"10.4007\/annals.2004.160.781"},{"key":"27_CR3","series-title":"Cambridge Studies in Advanced Mathematics","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139175319","volume-title":"Finite Group Theory","author":"M Aschbacher","year":"2000","unstructured":"Aschbacher, M.: Finite Group Theory. Cambridge Studies in Advanced Mathematics, 2nd edn. Cambridge University Press, Cambridge (2000)","edition":"2"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Szemer\u00e9di, E.: On the complexity of matrix group problems i. In: IEEE Annual Symposium on Foundations of Computer Science (1984)","DOI":"10.1109\/SFCS.1984.715919"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"493","DOI":"10.4171\/ggd\/666","volume":"16","author":"L Bartholdi","year":"2022","unstructured":"Bartholdi, L., Groth, T., Lysenok, I.: Commutator width in the first Grigorchuk group. Groups Geom. Dyn. 16, 493\u2013522 (2022)","journal-title":"Groups Geom. Dyn."},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/0021-8693(81)90265-9","volume":"68","author":"LP Comerford","year":"1981","unstructured":"Comerford, L.P., Edmunds, C.C.: Quadratic equations over free groups and free products. J. Algebra 68, 276\u2013297 (1981)","journal-title":"J. Algebra"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Cram\u00e9r, H.: On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica 2(1), 23\u201346 (1936). http:\/\/eudml.org\/doc\/205441","DOI":"10.4064\/aa-2-1-23-46"},{"issue":"2","key":"27_CR8","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0040-9383(81)90033-1","volume":"20","author":"M Culler","year":"1981","unstructured":"Culler, M.: Using surfaces to solve equations in free groups. Topology 20(2), 133\u2013145 (1981)","journal-title":"Topology"},{"key":"27_CR9","doi-asserted-by":"publisher","unstructured":"Diekert, V., Robson, J.: Quadratic Word Equations, pp. 314\u2013326. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-3-642-60207-8_28","DOI":"10.1007\/978-3-642-60207-8_28"},{"key":"27_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"1","key":"27_CR11","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0890-5401(02)93173-1","volume":"178","author":"M Goldmann","year":"2002","unstructured":"Goldmann, M., Russell, A.: The complexity of solving equations over finite groups. Inf. Comput. 178(1), 253\u2013262 (2002)","journal-title":"Inf. Comput."},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"Grigorchuk, R., Kurchanov, P.: On quadratic equations in free groups. In: Proceedings of the International Conference on Algebra Dedicated to the Memory of A. I. Malcev. Contemporary Mathematics, vol. 131, pp. 159\u2013171. AMS (1992)","DOI":"10.1090\/conm\/131.1\/1175769"},{"issue":"3","key":"27_CR13","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1142\/S0218196792000153","volume":"2","author":"R Grigorchuk","year":"1992","unstructured":"Grigorchuk, R., Lysionok, I.: A description of solutions of quadratic equations in hyperbolic groups. Int. J. Algebra Comput. 2(3), 237\u2013274 (1992)","journal-title":"Int. J. Algebra Comput."},{"key":"27_CR14","unstructured":"Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 4th edn. Oxford (1975)"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Holt, D.F., Eick, B., O\u2019Brien, E.A.: Handbook of Computational Group Theory. Chapman and Hall, Boca Raton (2005)","DOI":"10.1201\/9781420035216"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/s00224-008-9153-7","volume":"47","author":"O Kharlampovich","year":"2010","unstructured":"Kharlampovich, O., Lysenok, I., Myasnikov, A.G., Touikan, N.: The solvability problem for quadratic equations over free groups is NP-complete. Theor. Comput. Syst. 47, 250\u2013258 (2010)","journal-title":"Theor. Comput. Syst."},{"issue":"9","key":"27_CR17","doi-asserted-by":"publisher","first-page":"6207","DOI":"10.1090\/tran\/6829","volume":"369","author":"O Kharlampovich","year":"2017","unstructured":"Kharlampovich, O., Mohajeri, A., Taam, A., Vdovina, A.: Quadratic equations in hyperbolic groups are NP-complete. Trans. AMS 369(9), 6207\u20136238 (2017)","journal-title":"Trans. AMS"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"201","DOI":"10.4171\/ggd\/348","volume":"10","author":"I Lysenok","year":"2016","unstructured":"Lysenok, I., Miasnikov, A., Ushakov, A.: Quadratic equations in the Grigorchuk group. Groups Geom. Dyn. 10, 201\u2013239 (2016)","journal-title":"Groups Geom. Dyn."},{"key":"27_CR19","doi-asserted-by":"publisher","first-page":"1383","DOI":"10.1090\/proc\/12662","volume":"144","author":"I Lysenok","year":"2016","unstructured":"Lysenok, I., Ushakov, A.: Spherical quadratic equations in free metabelian groups. Proc. Am. Math. Soc. 144, 1383\u20131390 (2016)","journal-title":"Proc. Am. Math. Soc."},{"key":"27_CR20","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.jalgebra.2021.04.013","volume":"581","author":"I Lysenok","year":"2021","unstructured":"Lysenok, I., Ushakov, A.: Orientable quadratic equations in free metabelian groups. J. Algebra 581, 303\u2013326 (2021)","journal-title":"J. Algebra"},{"key":"27_CR21","doi-asserted-by":"crossref","unstructured":"Makanin, G.: Equations in a free group. Izvestiya AN SSSR, Ser. Mat. 46, 1199\u20131273 (1982). (Russian, English translation in Math USSR Izvestiya, 21, 3 (1983))","DOI":"10.1070\/IM1983v021n03ABEH001803"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Mandel, R., Ushakov, A.: Quadratic equations in metabelian Baumslag-Solitar groups. Int. J. Algebra Comput. (2023)","DOI":"10.1142\/S0218196723500558"},{"key":"27_CR23","unstructured":"Mattes, C., Ushakov, A., Wei\u00df, A.: Complexity of spherical equations in finite groups. arXiv eprints arxiv:2308.12841 (2023). https:\/\/doi.org\/10.48550\/arXiv.2308.12841"},{"key":"27_CR24","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/BF01212963","volume":"1","author":"P McKenzie","year":"1991","unstructured":"McKenzie, P., P\u00e9ladeau, P., Th\u00e9rien, D.: NC$${^1}$$: the automata-theoretic viewpoint. Comput. Complex. 1, 330\u2013359 (1991)","journal-title":"Comput. Complex."},{"key":"27_CR25","doi-asserted-by":"crossref","unstructured":"Schupp, P.E.: Quadratic equations in groups, cancellation diagrams on compact surfaces, and automorphisms of surface groups. In: Word Problems, II (Conference on Decision Problems in Algebra, Oxford, 1976), Stud. Logic Foundations Math, North-Holland, Amsterdam, vol. 95, pp. 347\u2013371 (1980)","DOI":"10.1016\/S0049-237X(08)71345-4"},{"key":"27_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, Berlin (1999). https:\/\/doi.org\/10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2024: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-52113-3_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T20:05:15Z","timestamp":1711569915000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-52113-3_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031521126","9783031521133"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-52113-3_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"7 February 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cochem","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 February 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 February 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.uni-trier.de\/index.php?id=90670&L=2","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"81","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.11","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}