13 citations · 27 across the 6 of their papers we have counts for
7 papers
Scale-Free Random SAT Instances
Carlos Ansótegui, Maria Luisa Bonet, Jordi Levy
We focus on the random generation of SAT instances that have properties similar to real-world instances. It is known that many industrial instances, even with a great number of var…
Community Structure in Industrial SAT Instances
Carlos Ansótegui, Maria Luisa Bonet, Jesús Giráldez-Cru +2
Modern SAT solvers have experienced a remarkable progress on solving industrial instances. Most of the techniques have been developed after an intensive experimental process. It is…
Short Proofs of the Kneser-Lovász Coloring Principle
James Aisenberg, Maria Luisa Bonet, Sam Buss +2
We prove that the propositional translations of the Kneser-Lovász theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs. We present a new counti…
The Fractal Dimension of SAT Formulas
C. Ansótegui, M. L. Bonet, J. Giráldez-Cru +1
Modern SAT solvers have experienced a remarkable progress on solving industrial instances. Most of the techniques have been developed after an intensive experimental testing proces…
Improved Separations of Regular Resolution from Clause Learning Proof Systems
Maria Luisa Bonet, Sam Buss, Jan Johannsen
We prove that the graph tautology formulas of Alekhnovich, Johannsen, Pitassi, and Urquhart have polynomial size pool resolution refutations that use only input lemmas as learned c…
An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning
Maria Luisa Bonet, Sam Buss
We prove that the graph tautology principles of Alekhnovich, Johannsen, Pitassi and Urquhart have polynomial size pool resolution refutations that use only input lemmas as learned…