3 citations · 5 across the 7 of their papers we have counts for
8 papers
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…
Notes on switching lemmas
Neil Thapen
We prove three switching lemmas, for random restrictions for which variables are set independently; for random restrictions where variables are set in blocks (both due to Hastad [H…
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…
Approximate counting and NP search problems
Leszek Aleksander Kołodziejczyk, Neil Thapen
We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoni…
How much randomness is needed for statistics?
Bjørn Kjos-Hanssen, Antoine Taveneaux, Neil Thapen
In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure , a choice needs to be made. One approach is to allow randomn…