Concept icon
Concept

Evaluating a sparse lifted factor without enumerating its scope

At one interpolation point store polynomials in Q[z,V]/(z^J,V^ell), at most J times ell rational coefficients. Here z is the local displacement from the interpolation point, while V tracks total h-order. To evaluate an equation, multiply the at most k substituted inputs in each listed monomial, then add these monomials to get L_i. Form h(L_i) and its successive powers to construct B_i, truncating the stored arrays throughout. This uses polynomially many rational operations in list length,k,J,ell. It does not enumerate the 2^{scope size} possible inputs, and it does not expand a multivariate polynomial in all original variables.

0

1

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math