{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:08Z","timestamp":1787337488726,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We design an algorithm for computing the generalized (algebraic circuits with root extracting; cf.\\ Pippenger [J. Comput. System Sci., 22 (1981), pp. 454--470], Ja'Ja' [Proc. 22nd IEEE FOCS, 1981, pp. 95--100], Grigoriev, Singer, and Yao [ SIAM J. Comput., 24 (1995), pp. 242--246]) additive complexity of any rational function. It is the first computability result of this sort on the additive complexity of algebraic circuits.<\/jats:p>","DOI":"10.1137\/s0097539793258313","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"694-701","source":"Crossref","is-referenced-by-count":0,"title":["Computing the Additive Complexity of Algebraic Circuits with Root Extracting"],"prefix":"10.1137","volume":"27","author":[{"given":"Dima","family":"Grigoriev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0205013"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01095643"},{"key":"R3","unstructured":"A. Chistov and D. Grigoriev,\n                      Subexponential\u2010time solving systems of algebraic equations\n                      , LOMI Preprints E\u20109\u201083, E\u201010\u201083, Steklov Math. Institute, 1983."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90014-7"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02104745"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"D. Grigor\u2019ev, Complexity of quantifier elimination in the theory of ordinary differential equations, Lecture Notes in Comput. Sci., Vol. 378, Springer, Berlin, 1989, 11\u20132591m:12009","DOI":"10.1007\/3-540-51517-8_81"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and M. Karpinski,\n                      Algorithms for sparse rational interpolation\n                      , in Proc. ACM ISSAC, 1991, pp. 7\u201313.","DOI":"10.1145\/120694.120696"},{"key":"R8","unstructured":"Dima Grigoriev, Marek Karpinski, Michael Singer, Interpolation of sparse rational functions without knowing bounds on exponents, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 840\u201384692k:65015"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194069"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"D. Grigoriev, M. Karpinski, M. Singer, Computational complexity of sparse real algebraic function interpolation, Progr. Math., Vol. 109, Birkh\u00e4user Boston, Boston, MA, 1993, 91\u201310494g:68055","DOI":"10.1007\/978-1-4612-2752-6_7"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793245015"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. Ja\u2019Ja\u2019,\n                      Computations of algebraic functions with root extractions\n                      , in Proc. 22nd IEEE FOCS, 1981, pp. 95\u2013100.","DOI":"10.1109\/SFCS.1981.14"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0222076"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"A. Khovanski,\n                      Fewnomials\n                      , AMS Transl. Math. Monogr. 88, 1991.","DOI":"10.1090\/mmono\/088"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90043-X"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0214014"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1976.65.485"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0208028"},{"key":"R19","first-page":"31","volume":"3","author":"Seidenberg A.","year":"1956","journal-title":"Univ. California Publ. Math. (N.S.)"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90068-7"},{"key":"R21","unstructured":"J. P. van de Wiele,\n                      Complexit\u00e9 additive et z\u00e9ros des polyn\u00f4mes \u00e0 coefficients r\u00e9els et complexes\n                      , Rapport de Recherche Laboria No 292, Mars 1978."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793258313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:37Z","timestamp":1787336017000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793258313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793258313"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793258313","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}