{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:53Z","timestamp":1750309133389,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T00:00:00Z","timestamp":1701302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Simons Collaboration on Algorithms and Geometry"},{"name":"NSF","award":["CF-1909683"],"award-info":[{"award-number":["CF-1909683"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions such as polynomial factorization and modular composition. And while\n            <jats:italic>nearly linear time<\/jats:italic>\n            algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck [\n            <jats:xref ref-type=\"bibr\">7<\/jats:xref>\n            ], fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state-of-the-art for this problem, Umans [\n            <jats:xref ref-type=\"bibr\">25<\/jats:xref>\n            ] and Kedlaya &amp; Umans [\n            <jats:xref ref-type=\"bibr\">16<\/jats:xref>\n            ] gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields, respectively, provided that the number of variables\n            <jats:italic>n<\/jats:italic>\n            is at most\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(d^{o(1)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            where the degree of the input polynomial in every variable is less than\n            <jats:italic>d<\/jats:italic>\n            . They also stated the question of designing fast algorithms for the large variable case (i.e.,\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n \\notin d^{o(1)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            ) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {F}_{q}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            of characteristic\n            <jats:italic>p<\/jats:italic>\n            , which evaluates an\n            <jats:italic>n<\/jats:italic>\n            -variate polynomial of degree less than\n            <jats:italic>d<\/jats:italic>\n            in each variable on\n            <jats:italic>N<\/jats:italic>\n            inputs in time\n            <jats:disp-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\begin{equation*} \n\\left((N + d^n)^{1 + o(1)}\\text{poly}(\\log q, d, n, p)\\right),\n\\end{equation*}\\)<\/jats:tex-math>\n            <\/jats:disp-formula>\n            provided that\n            <jats:italic>p<\/jats:italic>\n            is at most\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            , and\n            <jats:italic>q<\/jats:italic>\n            is at most (exp (exp (exp (...(exp (\n            <jats:italic>d<\/jats:italic>\n            ))))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g.,\n            <jats:italic>n<\/jats:italic>\n            \u2209\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            ), this is the first nearly linear time algorithm for this problem over any (large enough) field.\n          <\/jats:p>\n          <jats:p>Our algorithm is based on elementary algebraic ideas, and this algebraic structure naturally leads to the following two independently interesting applications:<\/jats:p>\n          <jats:p>\n            \u2014 We show that there is an\n            <jats:italic>algebraic<\/jats:italic>\n            data structure for univariate polynomial evaluation with nearly linear space complexity and sublinear time complexity over finite fields of small characteristic and quasipolynomially bounded size. This provides a counterexample to a conjecture of Miltersen [\n            <jats:xref ref-type=\"bibr\">21<\/jats:xref>\n            ] who conjectured that over small finite fields, any algebraic data structure for polynomial evaluation using polynomial space must have linear query complexity.\n          <\/jats:p>\n          <jats:p>\n            \u2014 We also show that over finite fields of small characteristic and quasipolynomially bounded size, Vandermonde matrices are not rigid enough to yield size-depth tradeoffs for linear circuits via the current quantitative bounds in Valiant\u2019s program [\n            <jats:xref ref-type=\"bibr\">26<\/jats:xref>\n            ]. More precisely, for every fixed prime\n            <jats:italic>p<\/jats:italic>\n            , we show that for every constant \u025b &gt; 0, and large enough\n            <jats:italic>n<\/jats:italic>\n            , the rank of any\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n \\times n\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            Vandermonde matrix\n            <jats:italic>V<\/jats:italic>\n            over the field\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {F}_{p^a}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            can be reduced to (\n            <jats:italic>n<\/jats:italic>\n            \/exp (\u03a9 (poly(\u025b)log\n            <jats:sup>0.53<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ))) by changing at most\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u0398 (\u025b)<\/jats:sup>\n            entries in every row of\n            <jats:italic>V<\/jats:italic>\n            , provided\n            <jats:italic>a<\/jats:italic>\n            \u2264 poly(log\n            <jats:italic>n<\/jats:italic>\n            ). Prior to this work, similar upper bounds on rigidity were known only for special Vandermonde matrices. For instance, the Discrete Fourier Transform matrices and Vandermonde matrices with generators in a geometric progression [\n            <jats:xref ref-type=\"bibr\">9<\/jats:xref>\n            ].\n          <\/jats:p>","DOI":"10.1145\/3625226","type":"journal-article","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T12:06:59Z","timestamp":1695384419000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-7869-377X","authenticated-orcid":false,"given":"Vishwas","family":"Bhargava","sequence":"first","affiliation":[{"name":"Cheriton School of Computer Science, University of 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":"California Institute of Technology, 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, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9972-0408","authenticated-orcid":false,"given":"Chandra Kanta","family":"Mohapatra","sequence":"additional","affiliation":[{"name":"Computer Science &amp; Engineering, IIT Bombay, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,11,30]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451008"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00067"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055484"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00084"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0513-7"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80029-2"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a008"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a020"},{"key":"e_1_3_4_11_2","author":"Dvir Zeev","year":"2021","unstructured":"Zeev Dvir and Allen Liu. 2021. personal communication.","journal-title":"personal communication"},{"key":"e_1_3_4_12_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. Retrieved from http:\/\/hdl.handle.net\/1721.1\/89843"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303207"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/945759"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0144-9"},{"key":"e_1_3_4_16_2","volume-title":"Extremal Combinatorics: With Applications in Computer Science (1st ed.)","author":"Jukna Stasys","year":"2010","unstructured":"Stasys Jukna. 2010. Extremal Combinatorics: With Applications in Computer Science (1st ed.). Springer Publishing Company, Incorporated."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/08073408X"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2021.68"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00008-6"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1786"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/11750321_28"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)80032-5"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_49"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00190-7"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374445"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_135"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2021.101574"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2022.101693"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3625226","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3625226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:03Z","timestamp":1750287003000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3625226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,30]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3625226"],"URL":"https:\/\/doi.org\/10.1145\/3625226","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2023,11,30]]},"assertion":[{"value":"2022-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}