2026-07-20T14:36:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24557 2025-12-16T14:00:47Z ddc:004 open_access

A Simple Algorithm for Trimmed Multipoint Evaluation Fischer, Nick Kallmayer, Melvin Wennmann, Leo Algebraic Algorithms Multipoint Evaluation Interpolation LU Decomposition 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nick Fischer and Melvin Kallmayer and Leo Wennmann 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.89 urn:nbn:de:0030-drops-245574 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.89 eng https://creativecommons.org/licenses/by/4.0/legalcode