{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:54:27Z","timestamp":1787385267750,"version":"build-2736575974"},"reference-count":9,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1995,4]]},"abstract":"<jats:p>Let $\\rho$ be a set of algebraic expressions constructed with radicals and arithmetic operations, and which generate the splitting field F of some polynomial. Let $N_{\\beta}(\\rho)$ be the minimum total number of root-takings and exponentiations used in any straightline program for computing the functions in $\\rho$ by taking roots, exponentials, logarithms, and performing arithmetic operations. In this paper it is proved that $N_{\\beta}(\\rho) = v(G)$, where $v(G)$ is the minimum length of any cyclic Jordan-H\u00f6lder tower for the Galois group G of F. This generalizes a result of Ja\u2019Ja\u2019 [Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, 1981, pp. 95\u2013100], and shows that the inclusion of certain new primitives, such as taking exponentials and logarithms, does not improve the cost of computing such expressions as compared with programs that use only root-takings.<\/jats:p>","DOI":"10.1137\/s0097539793245015","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:42:53Z","timestamp":1109227373000},"page":"242-246","source":"Crossref","is-referenced-by-count":4,"title":["On Computing Algebraic Functions Using Logarithms and Exponentials"],"prefix":"10.1137","volume":"24","author":[{"given":"Dima","family":"Grigoriev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Singer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Yao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","unstructured":"D. Grigoriev, M. Karpinski,  Computation of the Additive Complexity of Algebraic Circuits with Root Extracting, Tech. Report, TR-92-079, International Computer Science Institute, Berkeley, CA,  1992"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"J. Ja' Ja',  Computation of algebraic functions with root extractions,  Proceedings of 22nd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press,  1981,  95\u2013100","DOI":"10.1109\/SFCS.1981.14"},{"key":"R3","unstructured":"Irving Kaplansky, An introduction to differential algebra, Actualit\u00e9s Sci. Ind., No. 1251 = Publ. Inst. Math. Univ. Nancago, No. 5, Hermann, Paris, 1957, 63\u201320:1770083.03301"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1952-0049883-8"},{"key":"R5","volume-title":"Differential algebra and algebraic groups","author":"Kolchin E. R.","year":"1973"},{"key":"R6","volume-title":"Algebra","author":"Lang Serge","year":"1984"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90043-X"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90015-3"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Michael Ian Shamos, Gideon Yuval,  Lower bounds from complex function theory,  17th Annual Symposium on Foundations of Computer Science (Houston, Tex., 1976), IEEE Comput. Soc., Long Beach, Calif.,  1976,  268\u2013273 57:14603","DOI":"10.1109\/SFCS.1976.19"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793245015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:36Z","timestamp":1787337816000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793245015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,4]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,4]]}},"alternative-id":["10.1137\/S0097539793245015"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793245015","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,4]]}}}