claimroutine
Sparsify with sigma about 1/sqrt(log n)
Statement (paper)
For , applying Lemma with , where , yields a tree with nodes and polynomial depth, in which every leaf has occurrence bound and at most nonempty clauses.
In plain English
For , taking with in the sparsification lemma gives a polynomial-depth tree with nodes. Every leaf has occurrence bound and at most nonempty clauses.
Why it's here
This instantiates the sparsification lemma at a specific , trading an branching cost for leaves whose variable occurrences are only polylogarithmic in . Hence each leaf is a sparse -CNF with at most nonempty clauses, which the later leaf-counting steps and the time accounting rely on.
Classified routine:
This is a direct instantiation of the paper's sparsification lemma (lem-sparsify, in the style of the Impagliazzo–Paturi–Zane / Calabro–Impagliazzo–Paturi sparsification lemma) at σ≈1/√log n. The only work is substituting the parameter and simplifying the resulting bounds.