Fast Multivariate Multipoint Evaluation Over All Finite Fields Article Swipe

MAKE IMPACT

Vishwas Bhargava , Sumanta Ghosh , Zeyu Guo , Mrinal Kumar , Chris Umans · YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2205.00342

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 $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of degree less than $d$ in each variable at $N$ points in time \[ (d^m+N)^{1+o(1)}\cdot\poly(m,d,\log|\mathbb{F}|) \] for all $m\in\N$ and all sufficiently large $d\in\mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables $m$ is at most $d^{o(1)}$ 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 \emph{too} large and has characteristic less than $d^{o(1)}$. 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. 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örklund, Kaski and Williams (IPEC 2017, 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. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, avoids the use of the Bombieri--Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in $d$ of bounded \textit{height}.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2205.00342

PDF

https://arxiv.org/pdf/2205.00342

OA Status

green

Cited By

2

Related Works

10

OpenAlex ID

https://openalex.org/W4225401169

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4225401169

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2205.00342

Digital Object Identifier

Title

Fast Multivariate Multipoint Evaluation Over All Finite Fields

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2022

Year of publication

Publication date

2022-04-30

Full publication date if available

Authors

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans

List of authors in order

Landing page

https://arxiv.org/abs/2205.00342

Publisher landing page

PDF URL

https://arxiv.org/pdf/2205.00342

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2205.00342

Direct OA link when available

Concepts

Finite field, Mathematics, Multivariate statistics, Polynomial, Discrete mathematics, Field (mathematics), Combinatorics, Degree (music), Random variate, Constraint (computer-aided design), Random variable, Statistics, Pure mathematics, Physics, Mathematical analysis, Geometry, Acoustics

Top concepts (fields/topics) attached by OpenAlex

Cited by

2

Total citation count in OpenAlex

Citations by year (recent)

2024: 1, 2023: 1

Per-year citation counts (last 5 years)

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload