Concept icon
Concept

Using the sharper sparse-system counter in the existing SAT reductions

Conditional on the contraction theorem, choose sigma=1/ceil(sqrt(lambda)) in disjoint sparsification, lambda=ceil(log2 n). The tree has polynomial depth and 2^{O(n/sqrt(lambda))} times polynomially many nodes; leaf occurrence is polylogarithmic. The reviewed greedy parity procedure queries at most 6n degree-k equations with polylogarithmically many monomials each, including unsuccessful candidates. Replace its previous common-zero evaluator by the sharper conditional counter. The polylogarithmic logarithm of candidate overhead and the leaf-count exponent fit within O_k(n log log n/sqrt(log n)). Count one leaf and query at a time, adding disjoint counts in n+1 bits. The reduction is noncircular because its queried primitive accepts arbitrary sparse systems.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math