Tinted, detached, and lazy CNF-XOR solving and its applications to counting and sampling
Given a Boolean formula, the problem of counting seeks to estimate the number of solutions
of F while the problem of uniform sampling seeks to sample solutions uniformly at random …
of F while the problem of uniform sampling seeks to sample solutions uniformly at random …
Preprocessing in SAT solving
Preprocessing has become a key component of the Boolean satisfiability (SAT) solving
workflow. In practice, preprocessing is situated between the encoding phase and the solving …
workflow. In practice, preprocessing is situated between the encoding phase and the solving …
Certifying parity reasoning efficiently using pseudo-Boolean proofs
S Gocht, J Nordström - Proceedings of the AAAI Conference on Artificial …, 2021 - ojs.aaai.org
The dramatic improvements in combinatorial optimization algorithms over the last decades
have had a major impact in artificial intelligence, operations research, and beyond, but the …
have had a major impact in artificial intelligence, operations research, and beyond, but the …
Approximating complex arithmetic circuits with formal error guarantees: 32-bit multipliers accomplished
We present a novel method allowing one to approximate complex arithmetic circuits with
formal guarantees on the approximation error. The method integrates in a unique way formal …
formal guarantees on the approximation error. The method integrates in a unique way formal …
[HTML][HTML] The configurable SAT solver challenge (CSSC)
It is well known that different solution strategies work well for different types of instances of
hard combinatorial problems. As a consequence, most solvers for the propositional …
hard combinatorial problems. As a consequence, most solvers for the propositional …
Clausal proofs for pseudo-Boolean reasoning
When augmented with a Pseudo-Boolean (PB) solver, a Boolean satisfiability (SAT) solver
can apply apply powerful reasoning methods to determine when a set of parity or cardinality …
can apply apply powerful reasoning methods to determine when a set of parity or cardinality …
Approximate model counting
Abstract Model counting, or counting solutions of a set of constraints, is a fundamental
problem in Computer Science with diverse applications. Since exact counting is …
problem in Computer Science with diverse applications. Since exact counting is …
Exploring SAT for cryptanalysis:(quantum) collision attacks against 6-round SHA-3
In this work, we focus on collision attacks against instances of SHA-3 hash family in both
classical and quantum settings. Since the 5-round collision attacks on SHA3-256 and other …
classical and quantum settings. Since the 5-round collision attacks on SHA3-256 and other …
ApproxASP–a scalable approximate answer set counter
Abstract Answer Set Programming (ASP) is a framework in artificial intelligence and
knowledge representation for declarative modeling and problem solving. Modern ASP …
knowledge representation for declarative modeling and problem solving. Modern ASP …
Engineering an efficient PB-XOR solver
Despite the NP-completeness of Boolean satisfiability, modern SAT solvers are routinely
able to handle large practical instances, and consequently have found wide ranging …
able to handle large practical instances, and consequently have found wide ranging …