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
Tags
Math
Related
Why multiplying child contractions and summing mode tuples gives the parent evaluation
Reconstructing each call from correct children and then recovering the root
Counting the entire recursion tree rather than only one path
Combining the tuple bound with tapered precision
Enumerating weighted tuples without storing the complete list
Related
Why multiplying child contractions and summing mode tuples gives the parent evaluation
Reconstructing each call from correct children and then recovering the root
Counting the entire recursion tree rather than only one path
Combining the tuple bound with tapered precision
Enumerating weighted tuples without storing the complete list