Concept icon
Concept

Conditional sharper counting bound for a sparse polynomial system

Assume the fast-contraction theorem. Use s=n nu, P0=ell=n+1 for each incidence network. There are 2J vertices and O_(k,c)(s) wires. For fixed k,c and large enough n, its maximum degree n^(3/4) lambda^{O_(k,c)(1)} and entry cost satisfy the theorem bounds involving s^(9/10). Each contraction then has exponent O_(k,c)(n nu/sqrt(lambda)). High-incidence branches add O(n/sqrt(lambda)); degree arrays add O_(k,c)(sqrt(n) log n). Both are absorbed in the same exponent. Stream branches and arrays to preserve polynomial space. Small failing sizes use exhaustive counting. This verifies the application conditions, not the separate contraction theorem.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math