Concept
Why every candidate query fits the sparse common-zero counter
Initial rows number at most 3n; at most 3n further rows are ever included, so every candidate has at most 6n equations. A row mentioning at most s clauses expands to at most 2^k s monomials of degree at most k on the ORIGINAL n variables. Initial row length is at most D0 and added-list length is P. If B is bounded by a fixed power of log n for fixed k, both P and D0 are polylogarithmic, so one fixed sparsity constant c covers all queries, including discarded candidates. At most 3n(2m)^P+1 counts suffice. There is no circular SAT oracle: the queried primitive was derived for sparse polynomial systems independently of this reduction.
0
1
Updated 2026-11-08
Tags
Math