3 citations · 5 across the 7 of their papers we have counts for
4 papers · 1 filter
The strength of the dominance rule
Leszek Aleksander Kołodziejczyk, Neil Thapen
It has become standard that, when a SAT solver decides that a CNF is unsatisfiable, it produces a certificate of unsatisfiability in the form of a refutation of in some pro…
First-Order Reasoning and Efficient Semi-Algebraic Proofs
Fedor Part, Neil Thapen, Iddo Tzameret
Semi-algebraic proof systems such as sum-of-squares (SoS) have attracted a lot of attention recently due to their relation to approximation algorithms: constant degree semi-algebra…
DRAT and Propagation Redundancy Proofs Without New Variables
Sam Buss, Neil Thapen
We study the complexity of a range of propositional proof systems which allow inference rules of the form: from a set of clauses derive the set of clauses where…
The strength of replacement in weak arithmetic
Stephen Cook, Neil Thapen
The replacement (or collection or choice) axiom scheme asserts bounded quantifier exchange. We prove the independence of this scheme from various weak theories of arithmetic, somet…