Certified core-guided MaxSAT solving
In the last couple of decades, developments in SAT-based optimization have led to highly
efficient maximum satisfiability (MaxSAT) solvers, but in contrast to the SAT solvers on which …
efficient maximum satisfiability (MaxSAT) solvers, but in contrast to the SAT solvers on which …
Separations in proof complexity and TFNP
It is well-known that Resolution proofs can be efficiently simulated by Sherali–Adams (SA)
proofs. We show, however, that any such simulation needs to exploit huge coefficients …
proofs. We show, however, that any such simulation needs to exploit huge coefficients …
Clique is hard on average for unary Sherali-Adams
SF De Rezende, A Potechin… - 2023 IEEE 64th Annual …, 2023 - ieeexplore.ieee.org
We prove that unary Sherali-Adams requires proofs of size n^Ω(d) to rule out the existence
of an n^Θ(1)-clique in Erdős-Rényi random graphs whose maximum clique is of size …
of an n^Θ(1)-clique in Erdős-Rényi random graphs whose maximum clique is of size …
Colourful TFNP and propositional proofs
B Davis, R Robere - 38th Computational Complexity Conference …, 2023 - drops.dagstuhl.de
Recent work has shown that many of the standard TFNP classes-such as PLS, PPADS,
PPAD, SOPL, and EOPL-have corresponding proof systems in propositional proof …
PPAD, SOPL, and EOPL-have corresponding proof systems in propositional proof …
Proofs and certificates for Max-SAT
Current Max-SAT solvers are able to efficiently compute the optimal value of an input
instance but they do not provide any certificate of its validity. In this paper, we present a tool …
instance but they do not provide any certificate of its validity. In this paper, we present a tool …
Towards a better understanding of (partial weighted) MaxSAT proof systems
J Larrosa, E Rollon - Theory and Applications of Satisfiability Testing–SAT …, 2020 - Springer
MaxSAT is a very popular language for discrete optimization with many domains of
application. While there has been a lot of progress in MaxSAT solvers during the last …
application. While there has been a lot of progress in MaxSAT solvers during the last …
Certified MaxSAT Preprocessing
Building on the progress in Boolean satisfiability (SAT) solving over the last decades,
maximum satisfiability (MaxSAT) has become a viable approach for solving NP-hard …
maximum satisfiability (MaxSAT) has become a viable approach for solving NP-hard …
Proving unsatisfiability with hitting formulas
Hitting formulas have been studied in many different contexts at least since [Iwama, 89]. A
hitting formula is a set of Boolean clauses such that any two of them cannot be …
hitting formula is a set of Boolean clauses such that any two of them cannot be …
Inferring Clauses and Formulas in Max-SAT
In this paper, we are interested in proof systems for Max-SAT and particularly in the
construction of Max-SAT equivalence-preserving transformations to infer information from a …
construction of Max-SAT equivalence-preserving transformations to infer information from a …
On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
I Bonacina, ML Bonet - Proceedings of the 37th Annual ACM/IEEE …, 2022 - dl.acm.org
We characterize the strength of the algebraic proof systems Sherali-Adams () and
Nullstellensatz () in terms of Frege-style proof systems. Unlike bounded-depth Frege, has …
Nullstellensatz () in terms of Frege-style proof systems. Unlike bounded-depth Frege, has …