Concept icon
Concept

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

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math