A Simple Algorithm for Trimmed Multipoint Evaluation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917261826064384 |
|---|---|
| author | Fischer, Nick Kallmayer, Melvin Wennmann, Leo |
| author_facet | Fischer, Nick Kallmayer, Melvin Wennmann, Leo |
| contents | Evaluating a polynomial on a set of points is a fundamental task in computer algebra. In this work, we revisit a particular variant called trimmed multipoint evaluation: given an $n$-variate polynomial with bounded individual degree $d$ and total degree $D$, the goal is to evaluate it on a natural class of input points. This problem arises as a key subroutine in recent algorithmic results [Dinur; SODA '21], [Dell, Haak, Kallmayer, Wennmann; SODA '25]. It is known that trimmed multipoint evaluation can be solved in near-linear time [van der Hoeven, Schost; AAECC '13] by a clever yet somewhat involved algorithm. We give a simple recursive algorithm that avoids heavy computer-algebraic machinery, and can be readily understood by researchers without specialized background. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00196 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simple Algorithm for Trimmed Multipoint Evaluation Fischer, Nick Kallmayer, Melvin Wennmann, Leo Data Structures and Algorithms Evaluating a polynomial on a set of points is a fundamental task in computer algebra. In this work, we revisit a particular variant called trimmed multipoint evaluation: given an $n$-variate polynomial with bounded individual degree $d$ and total degree $D$, the goal is to evaluate it on a natural class of input points. This problem arises as a key subroutine in recent algorithmic results [Dinur; SODA '21], [Dell, Haak, Kallmayer, Wennmann; SODA '25]. It is known that trimmed multipoint evaluation can be solved in near-linear time [van der Hoeven, Schost; AAECC '13] by a clever yet somewhat involved algorithm. We give a simple recursive algorithm that avoids heavy computer-algebraic machinery, and can be readily understood by researchers without specialized background. |
| title | A Simple Algorithm for Trimmed Multipoint Evaluation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.00196 |