Concept icon
Concept

How the three exponent terms shrink together

For fixed beta, the recipe gives R/Q=O_beta(nu/sqrt(lambda)) and log2(2Q/R)=O(nu), so their product is O_beta(nu^2/sqrt(lambda)). Also tau=1/(r*lambda) and log2(2D+1)=O(lambda), giving tau*log2(2D+1)=O(1/r). Finally 1/r=O(nu^2/sqrt(lambda)). Thus all three terms sum to O_beta(nu^2/sqrt(lambda)), which tends to zero. If total factor degree is O(n), all layout/data sizes are polynomial, and BOTH factor evaluation and coefficient arithmetic, including accumulation and interpolation, have polynomial bit cost, the routine takes a polynomial factor times 2^{O_beta(n*(log log n)^2/sqrt(log n))}. The separate bit-complexity branch must justify the arithmetic hypothesis; this is not yet a result for arbitrary SAT input.

0

1

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math