Lifting Nullstellensatz Degree to Monotone Span Program Size
summary
States a concrete equivalence: for any unsatisfiable CNF the Nullstellensatz degree of refutation lifts (via a constant-size gadget) to the monotone span program size of a derived monotone function up to an exponent. Proof uses a gadget composition that turns polynomial degree into matrix rank, a tensor/rank analysis and a duality between an algebraic tiling view and Nullstellensatz proofs (the rank measure). Consequences include field-uniform exponential lower bounds (previously only over R), ST‑connectivity lower bounds like n^{Θ(log n)} and some functions with 2^{Ω(n)} span size, so the construction works.
AI-written summary · about