Branching on high-incidence variables before constructing a layout
A sparse equation may read few variables even though one variable occurs in many equations. Include a neutral singleton factor for every declared variable, and let M be total scope incidences. For n>=20 put lambda=ceil(log2 n) and b0=ceil(M/n)ceil(sqrt(lambda)). Fix every variable occurring in more than b0 scopes. There are at most M/b0<=n/sqrt(lambda) such variables, hence at most 2^{n/sqrt(lambda)} branches. Substitute the fixed bits over F_2 and cancel duplicate monomials BEFORE rebuilding integer lifts. The free-variable count n_prime is at least n/2. The branches are disjoint, so their exact counts add; neither sparse degree nor monomial-list length increases under restriction.
0
1
Tags
Math