{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T03:49:06Z","timestamp":1775533746107,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T00:00:00Z","timestamp":1775520000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T00:00:00Z","timestamp":1775520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Tokyo University of Science"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2026,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Given a multivariate polynomial\n                    <jats:italic>f<\/jats:italic>\n                    , we consider an approximate decomposition in the Hamming distance, that is,\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$${f}{=} {g} {\\circ } {h} \\,{+ \\, \\delta },$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>f<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi>g<\/mml:mi>\n                            <mml:mo>\u2218<\/mml:mo>\n                            <mml:mi>h<\/mml:mi>\n                            <mml:mspace\/>\n                            <mml:mrow>\n                              <mml:mo>+<\/mml:mo>\n                              <mml:mspace\/>\n                              <mml:mi>\u03b4<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>,<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    where\n                    <jats:italic>g<\/jats:italic>\n                    is a univariate polynomial,\n                    <jats:italic>h<\/jats:italic>\n                    and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$${\\delta }$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b4<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    are multivariate polynomials, and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$${\\delta }$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b4<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    has few terms. We propose an algorithm for computing an approximate decomposition and introduce its application to multivariate Horner\u2019s scheme.\n                  <\/jats:p>","DOI":"10.1007\/s11786-025-00621-5","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T02:52:45Z","timestamp":1775530365000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Approximate Decomposition of a Multivariate Polynomial and Its Application"],"prefix":"10.1007","volume":"20","author":[{"given":"Rikuna","family":"Tokuda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Sekigawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"issue":"2","key":"621_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0747-7171(85)80012-2","volume":"1","author":"DR Barton","year":"1985","unstructured":"Barton, D.R., Zippel, R.: Polynomial decomposition algorithms. J. Symb. Comput. 1(2), 159\u2013168 (1985)","journal-title":"J. Symb. Comput."},{"issue":"5","key":"621_CR2","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0747-7171(89)80027-6","volume":"7","author":"D Kozen","year":"1989","unstructured":"Kozen, D., Landau, S.: Polynomial decomposition algorithms. J. Symb. Comput. 7(5), 445\u2013456 (1989)","journal-title":"J. Symb. Comput."},{"issue":"3","key":"621_CR3","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0747-7171(08)80014-4","volume":"9","author":"J von zur Gathen","year":"1990","unstructured":"von zur Gathen, J.: Functional decomposition of polynomials: the tame case. J. Symb. Comput. 9(3), 281\u2013299 (1990)","journal-title":"J. Symb. Comput."},{"issue":"5","key":"621_CR4","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/S0747-7171(08)80054-5","volume":"10","author":"J von zur Gathen","year":"1990","unstructured":"von zur Gathen, J.: Functional decomposition of polynomials: the wild case. J. Symb. Comput. 10(5), 437\u2013452 (1990)","journal-title":"J. Symb. Comput."},{"issue":"1\/2","key":"621_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/2644288.2644292","volume":"48","author":"R Blankertz","year":"2014","unstructured":"Blankertz, R.: A polynomial time algorithm for computing all minimal decompositions of a polynomial. ACM Commun. Comput. Algebra 48(1\/2), 13\u201323 (2014)","journal-title":"ACM Commun. Comput. Algebra"},{"key":"621_CR6","doi-asserted-by":"crossref","unstructured":"Allem, L.E., Capaverde, J.G., van Hoeij, M., Szutkoski, J.: Functional decomposition using principal subfields. In: Proceedings of the 2017 International Symposium on Symbolic and Algebraic Computation, Association for Computing Machinery, New York, NY, United States, pp. 421\u2013428 (2017)","DOI":"10.1145\/3087604.3087608"},{"key":"621_CR7","unstructured":"Dickerson, M.T.: The functional decomposition of polynomials. Ph.D. thesis, Cornell University. Computer Science Technical Report TR89-1023, Cornell University (1989)"},{"issue":"1","key":"621_CR8","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/s00200-003-0122-8","volume":"14","author":"J von zur Gathen","year":"2003","unstructured":"von zur Gathen, J., Gutierrez, J., Rubio, R.: Multivariate polynomial decomposition. Appl. Algebra Eng. Commun. Comput. 14(1), 11\u201331 (2003)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"issue":"12","key":"621_CR9","doi-asserted-by":"publisher","first-page":"1676","DOI":"10.1016\/j.jsc.2008.02.005","volume":"44","author":"J-C Faug\u00e8re","year":"2009","unstructured":"Faug\u00e8re, J.-C., Perret, L.: An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography. J. Symb. Comput. 44(12), 1676\u20131689 (2009)","journal-title":"J. Symb. Comput."},{"key":"621_CR10","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re, J.-C., Perret, L.: High order derivatives and decomposition of multivariate polynomials. In: Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, Association for Computing Machinery, New York, NY, United States, pp. 207\u2013214 (2009)","DOI":"10.1145\/1576702.1576732"},{"key":"621_CR11","doi-asserted-by":"crossref","unstructured":"Corless, R.M., Giesbrecht, M., Jeffrey, D.J., Watt, S.M.: Approximate polynomial decomposition. In: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, Association for Computing Machinery, New York, NY, United States, pp. 213\u2013219 (1999)","DOI":"10.1145\/309831.309939"},{"key":"621_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-7643-7984-1_7","volume-title":"Symbolic-Numeric Computation","author":"M Giesbrecht","year":"2007","unstructured":"Giesbrecht, M., May, J.: New algorithms for exact and approximate polynomial decomposition. In: Wang, D., Zhi, L. (eds.) Symbolic-Numeric Computation, pp. 99\u2013112. Birkh\u00e4user, Basel (2007)"},{"issue":"3","key":"621_CR13","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1145\/3637529.3637532","volume":"57","author":"H Sekigawa","year":"2023","unstructured":"Sekigawa, H.: An approximation algorithm for the nearest decomposable polynomial in the Hamming distance. ACM Commun. Comput. Algebra 57(3), 119\u2013122 (2023)","journal-title":"ACM Commun. Comput. Algebra"},{"issue":"1","key":"621_CR14","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548314000388","volume":"24","author":"J von zur Gathen","year":"2015","unstructured":"von zur Gathen, J.: Counting decomposable univariate polynomials. Comb. Probab. Comput. 24(1), 294\u2013328 (2015)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"621_CR15","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00200-011-0141-9","volume":"22","author":"J von zur Gathen","year":"2011","unstructured":"von zur Gathen, J.: Counting decomposable multivariate polynomials. Appl. Algebra Eng. Commun. Comput. 22(3), 165\u2013185 (2011)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"621_CR16","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1007\/s10543-014-0533-x","volume":"55","author":"J Czekansky","year":"2015","unstructured":"Czekansky, J., Sauer, T.: The multivariate Horner scheme revisited. BIT Numer. Math. 55, 1043\u20131056 (2015)","journal-title":"BIT Numer. Math."}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-025-00621-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11786-025-00621-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-025-00621-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T02:52:47Z","timestamp":1775530367000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11786-025-00621-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,7]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,12]]}},"alternative-id":["621"],"URL":"https:\/\/doi.org\/10.1007\/s11786-025-00621-5","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,7]]},"assertion":[{"value":"29 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"6"}}