{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:29:45Z","timestamp":1778128185515,"version":"3.51.4"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T00:00:00Z","timestamp":1718064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001502","name":"Department of Atomic Energy, Government of India","doi-asserted-by":"crossref","award":["12-R&D-TFR-5.01-0500"],"award-info":[{"award-number":["12-R&D-TFR-5.01-0500"]}],"id":[{"id":"10.13039\/501100001502","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"\n Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field\n \n \\(\\mathbb {F}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n that outputs the evaluations of an\n m<\/jats:italic>\n -variate polynomial of degree less than\n d<\/jats:italic>\n in each variable at\n N<\/jats:italic>\n points in time,\n \n \\(\\begin{equation*} \n(d^m+N)^{1+o(1)}\\cdot {{\\sf poly}}(m,d,\\log |\\mathbb {F}|),\n\\end{equation*}\\)<\/jats:tex-math>\n <\/jats:disp-formula>\n for all\n \n \\(m\\in \\mathbb {N}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and all sufficiently large\n \n \\(d\\in \\mathbb {N}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n A previous work of Kedlaya and Umans (FOCS 2008 and SICOMP 2011) achieved the same time complexity when the number of variables\n m<\/jats:italic>\n is at most\n \n \\(d^{o(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar, and Mohapatra (STOC 2022) answered this question when the underlying field is not\n too<\/jats:italic>\n large and has characteristic less than\n \n \\(d^{o(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields.\n <\/jats:p>\n Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Bj\u00f6rklund, Kaski, and Williams (IPEC 2017 and Algorithmica 2019), and that of Bhargava, Ghosh, Kumar, and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression.<\/jats:p>\n \n We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and, in particular, avoids the use of the Bombieri\u2013Vinogradov theorem. However, it requires a mild assumption that the field size is bounded by an exponential tower in\n d<\/jats:italic>\n of bounded\n height<\/jats:italic>\n . More specifically, our second algorithm solves the multivariate multipoint evaluation problem over a finite field\n \n \\(\\mathbb {F}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in time,\n \n \\(\\begin{equation*} \n(d^m+N)^{1+o(1)}\\cdot {{\\sf poly}}(m,d,\\log |\\mathbb {F}|),\n\\end{equation*}\\)<\/jats:tex-math>\n <\/jats:disp-formula>\n for all\n \n \\(m\\in \\mathbb {N}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and all sufficiently large\n \n \\(d\\in \\mathbb {N}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , provided that the size of the finite field\n \n \\(\\mathbb {F}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is at most\n \n \\((\\exp (\\exp (\\exp (\\cdots (\\exp (d)))))\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where the height of this tower of exponentials is fixed.\n <\/jats:p>","DOI":"10.1145\/3652025","type":"journal-article","created":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T11:52:20Z","timestamp":1711021940000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast Multivariate Multipoint Evaluation over All Finite Fields"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-7869-377X","authenticated-orcid":false,"given":"Vishwas","family":"Bhargava","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4892-4210","authenticated-orcid":false,"given":"Sumanta","family":"Ghosh","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7893-4346","authenticated-orcid":false,"given":"Zeyu","family":"Guo","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6430-0219","authenticated-orcid":false,"given":"Mrinal","family":"Kumar","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6390-9401","authenticated-orcid":false,"given":"Chris","family":"Umans","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519968"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0513-7"},{"key":"e_1_3_3_4_2","doi-asserted-by":"crossref","unstructured":"Enrico Bombieri. 1965. On the large sieve. Mathematika 12 2 (1965) 201\u2013225.","DOI":"10.1112\/S0025579300005313"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80029-2"},{"key":"e_1_3_3_6_2","volume-title":"Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs","author":"Forbes Michael","year":"2014","unstructured":"Michael Forbes. 2014. Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17364-6"},{"key":"e_1_3_3_8_2","unstructured":"Kiran Kedlaya. 2015. Lecture Notes for the Course \u2018Analytic Number Theory\u2019. Retrieved from https:\/\/kskedlaya.org\/papers\/ant-overall.pdf"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/08073408X"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0041-0"},{"key":"e_1_3_3_11_2","unstructured":"J. Maynard. 2012. On the Brun-Titchmarsh theorem. arXiv:1201.1777. Retrieved from https:\/\/arxiv.org\/abs\/1201.1777"},{"key":"e_1_3_3_12_2","article-title":"Primes in arithmetic progressions to large moduli I: Fixed residue classes","author":"Maynard James","year":"2020","unstructured":"James Maynard. 2020. Primes in arithmetic progressions to large moduli I: Fixed residue classes. arXiv:2006.06572. Retrieved from https:\/\/arxiv.org\/abs\/2006.06572","journal-title":"arXiv:2006.06572"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_49"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814549"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.4064\/aa-1-1-83-86"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374445"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2019.04.001"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2022.101693"},{"key":"e_1_3_3_19_2","first-page":"903","article-title":"The density hypothesis for the dirichlet L-series","volume":"29","author":"Vinogradov A. I.","year":"1965","unstructured":"A. I. Vinogradov. 1965. The density hypothesis for the dirichlet L-series. Izvest. Rossiisk. Akad. Nauk. Ser. Mat. 29 (1965), 903\u2013934.","journal-title":"Izvest. Rossiisk. Akad. Nauk. Ser. Mat."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01218882"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3652025","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3652025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:12Z","timestamp":1750291392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3652025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,11]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3652025"],"URL":"https:\/\/doi.org\/10.1145\/3652025","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,11]]},"assertion":[{"value":"2023-07-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}