{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T04:16:27Z","timestamp":1687925787975},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T00:00:00Z","timestamp":1669680000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T00:00:00Z","timestamp":1669680000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a uniform description of sets of <jats:italic>m<\/jats:italic> linear forms\nin <jats:italic>n<\/jats:italic> variables over the field of rational numbers whose computation\nrequires <jats:italic>m<\/jats:italic>(<jats:italic>n<\/jats:italic> \u2013 1) additions.\n<\/jats:p>","DOI":"10.1007\/s00037-022-00234-5","type":"journal-article","created":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T07:14:07Z","timestamp":1669706047000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On sets of linear forms of maximal complexity"],"prefix":"10.1007","volume":"32","author":[{"given":"Michael","family":"Kaminski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor E.","family":"Shparlinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Waldschmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,29]]},"reference":[{"key":"234_CR1","unstructured":"A. V. Aho, J. E. Hopcroft and J. D. Ulhnan, The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"234_CR2","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser, M. Clausen and A. Shokrollahi, Algebraic complexity\ntheory, Springer, Berlin, 1997.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"234_CR3","doi-asserted-by":"crossref","unstructured":"L. Fukshansky, \u2018Integral points of small height outside of a hypersurface\u2019, Monatsh. Math., 147 (2006), 25\u201341.","DOI":"10.1007\/s00605-005-0333-0"},{"key":"234_CR4","unstructured":"J. Hadamard, \u2019Sur le module maximum que puisse atteindre un\nd\u00e9terminant. C. R. Acad. Sci Paris 141 (1893), 1500\u20131501."},{"key":"234_CR5","unstructured":"J. Heintz and C.-P. Schnorr, \u2019Testing polynomials which are easy to compute\u2019. Int. Symp. on Logic and Algorithmic, Z\u00fcrich 1980, Monogr. L\u2019Enseign. Math., v. 30, 1982, Univ. Gen\u00e9ve, 237\u2013254. Preliminary version in Proc. 12th ACM Symposium on Theory of Computing, 1980 , 263\u2013272."},{"key":"234_CR6","unstructured":"M. Kaminski and I. E. Shparlinski, \u2018Sets of linear forms which are hard to compute\u2019, Proc. 46th Intern. Symp. on Math. Found. of Comp. Sci. (MFCS), Schloss Dagstuhl - Leibniz-Zentrum LIPIcs, vol. 202, F. Bonchi and S.J. Puglisi, eds., Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2021, 66:1\u201366:22."},{"key":"234_CR7","doi-asserted-by":"crossref","unstructured":"P. Koiran, \u2018Elimination of constants from machines over algebraically closed fields\u2019, J. Compl., 13 (1997), 65\u201382.","DOI":"10.1006\/jcom.1997.0433"},{"key":"234_CR8","doi-asserted-by":"crossref","unstructured":"T. Krick, L. M. Pardo and M. Sombra, \u2018Sharp estimates for the arithmetic Nullstellensatz\u2019, Duke Math. J., 109 3 (2001), 521\u2013528.","DOI":"10.1215\/S0012-7094-01-10934-4"},{"key":"234_CR9","doi-asserted-by":"crossref","unstructured":"L. Kronecker. \u2019Grundz\u00fcge einer arithmetischen Theorie der algebraischen Gr\u00f6ssen\u2019. J. reine angew. Math., 92 (1882), 1\u2013122.","DOI":"10.1515\/9783112342404-001"},{"key":"234_CR10","doi-asserted-by":"crossref","unstructured":"M. Mignotte, Mathematics for computer algebra, Springer-Verlag, Berlin, 1992.","DOI":"10.1007\/978-1-4613-9171-5"},{"key":"234_CR11","unstructured":"O. Perron, Algebra I (Die Grundlagen), Walter de Gruyter, Berlin, 1927."},{"key":"234_CR12","unstructured":"A. Ploski, \u2018Algebraic dependence of polynomials after O. Perron and some applications\u2019, Computational Commutative and Non-Commutative Algebraic Geometry, NATO Science Series, III: Computer and Systems Sciences, vol. 196, IOS Press, Amsterdam, 2005, 167\u2013173."},{"key":"234_CR13","doi-asserted-by":"crossref","unstructured":"J. E. Savage, \u2018An algorithm for the computation of linear forms\u2019, SIAM J. Comp., 3 (1974), 150\u2013158.","DOI":"10.1137\/0203011"},{"key":"234_CR14","doi-asserted-by":"crossref","unstructured":"J. T. Schwartz, \u2018Fast probabilistic algorithms for verification of polynomial identities\u2019, J. ACM, 27, (1980), 701\u2013717.","DOI":"10.1145\/322217.322225"},{"key":"234_CR15","doi-asserted-by":"crossref","unstructured":"A. Sert, \u2018Une version effective du th\u00e9or\u00e8me de Lindemann\u2013Weierstrass par les d\u00e9terminants d\u2019interpolation\u2019, J. Number Theory, 76 (1999), 94\u2013119.","DOI":"10.1006\/jnth.1998.2356"},{"key":"234_CR16","doi-asserted-by":"crossref","unstructured":"V. Strassen, \u2018Vermeidung von Divisionen\u2019, J. reine angew. Math., 264 (1973), 184\u2013202.","DOI":"10.1515\/crll.1973.264.184"},{"key":"234_CR17","doi-asserted-by":"crossref","unstructured":"V. Strassen, \u2018Polynomials with rational coefficients which are hard to compute\u2019, SIAM J. Comp., 3 (1974), 128\u2013149.","DOI":"10.1137\/0203010"},{"key":"234_CR18","doi-asserted-by":"crossref","unstructured":"R. Zippel, \u2018Probabilistic algorithms for sparse polynomials, Intern. Symp. on Symbolic and Algebraic Comp., 1979 , Lecture Notes in Computer Science, v.72, Springer, 1979, 216\u2013226.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00234-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-022-00234-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00234-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T17:04:02Z","timestamp":1687885442000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-022-00234-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,29]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["234"],"URL":"https:\/\/doi.org\/10.1007\/s00037-022-00234-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,29]]},"assertion":[{"value":"20 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"1"}}