Zobrazeno 1 - 10
of 97
pro vyhledávání: '"Thapen, Neil"'
It has become standard that, when a SAT solver decides that a CNF $\Gamma$ is unsatisfiable, it produces a certificate of unsatisfiability in the form of a refutation of $\Gamma$ in some proof system. The system typically used is DRAT, which is equiv
Externí odkaz:
http://arxiv.org/abs/2406.13657
Publikováno v:
In Annals of Pure and Applied Logic January 2025 176(1)
Autor:
Thapen, Neil
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 [Hastad 86]); and for a distribution appropriate for the bijective pigeo
Externí odkaz:
http://arxiv.org/abs/2202.05651
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-algebraic proofs lead to conjecturally optimal polynomial-time approximation
Externí odkaz:
http://arxiv.org/abs/2105.07531
Autor:
Buss, Sam, Thapen, Neil
Publikováno v:
Logical Methods in Computer Science, Volume 17, Issue 2 (April 23, 2021) lmcs:5750
We study the complexity of a range of propositional proof systems which allow inference rules of the form: from a set of clauses $\Gamma$ derive the set of clauses $\Gamma \cup \{ C \}$ where, due to some syntactic condition, $\Gamma \cup \{ C \}$ is
Externí odkaz:
http://arxiv.org/abs/1909.00520
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 reasoning is the bounded arithmetic theory $\mathrm{APC}_2$ of [Je\v{r}\'abek
Externí odkaz:
http://arxiv.org/abs/1812.10771
Publikováno v:
Annals of Pure and Applied Logic 165 (2014), no. 9, 1470--1483
In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure $\lambda $, a choice needs to be made. One approach is to allow randomness tests to access the measure $\lambda $ as an oracle (which
Externí odkaz:
http://arxiv.org/abs/1408.2862
We say that a graph with $n$ vertices is $c$-Ramsey if it does not contain either a clique or an independent set of size $c \log n$. We define a CNF formula which expresses this property for a graph $G$. We show a superpolynomial lower bound on the l
Externí odkaz:
http://arxiv.org/abs/1303.3166
Autor:
Cook, Stephen, Thapen, Neil
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, sometimes under a complexity assumption.
Externí odkaz:
http://arxiv.org/abs/cs/0409015