2 papers
cs.CC2026
A Degree--Size Relation for Resolution over Polynomials
Shuo Pang
For every constant-width CNF, we show that linear degree in polynomial calculus (PC) implies exponential size in resolution over constant-degree polynomials, over the same prime fi…
cs.LO2019
On CDCL-based proof systems with the ordered decision strategy
Nathan Mull, Shuo Pang, Alexander Razborov
We prove that conflict-driven clause learning SAT-solvers with the ordered decision strategy and the DECISION learning scheme are equivalent to ordered resolution. We also prove th…