Concept icon
Concept

Bounding the bit cost of one implicitly described packet entry

A packet has at most L affine row factors, each with polynomially many terms in root s. Enumerate one choice per row, retain choices with the requested target exponents, and sum their coefficients. This costs exp(O(L log s)) times polynomial coordinate-arithmetic work and uses polynomial space. Source-form powers are computed by repeated squaring, not repeated multiplication beta_Z times. With L<=s^(1/1000), the entry cost is exp(O(s^(9/10))) for sufficiently large s. Precision and every coordinate array stay polynomially bounded. This is a worst-case implicit-entry bound, not a claim that all packet coefficients are materialized.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math