Concept
Combining recovery weights with bounded rational arithmetic
Each weight E_t(0)(-t/alpha)^j, j<q_t, is a product of polynomially many rational factors with O(a) bits per factor. Its numerator and denominator therefore have polynomial bit length in M,L,a. There are polynomially many weights, so even multiplying their denominators gives a polynomial-bit common denominator. Combine coordinates exactly, cancel powers of two after addition, and reduce the remaining odd-denominator rationals modulo 2^p. Individual terms may have even denominators; reducing them modulo 2^p before the precision argument and rational combination would be invalid. Recovery is polynomial in the stated dimensions and precisions, not in their logarithms.
0
1
Updated 2026-11-08
Tags
Math