Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Events

The Taub Faculty of Computer Science Events and Talks

InPRocessing with Scaffolded Propagation Redundant Clauses
event speaker icon
Basel Khouri (M.Sc. Thesis Seminar)
event date icon
Tuesday, 15.12.2026, 13:00
event location icon
Taub 601 & Zoom
event speaker icon
Advisor: Assoc. Prof. Yakir Vizel

 Modern SAT solvers are, at their core, proof engines: when a formula is unsatisfiable, a run of the solver corresponds to a proof of this fact. The dominant algorithm, conflict-driven clause learning (CDCL), learns clauses by resolution, an inference rule that preserves logical equivalence: every learned clause is implied by the formula. Resolution is sound and complete, but it is a weak proof system. Some formulas, such as those encoding the pigeonhole principle, have only exponential-size resolution proofs. On these formulas CDCL cannot succeed, however well it is engineered. Stronger proof systems overcome this limitation by allowing steps that preserve only satisfiability, not logical equivalence. Propagation redundant (PR) clauses are a prominent example. A PR clause may exclude models of the formula, as long as some model remains. PR-based proof systems have short proofs of many formulas that are hard for resolution, without introducing new variables. The price is that checking whether a clause is PR is harder. The check requires a witness, which transforms every model of the formula that falsifies the clause into a model that satisfies it. Every clause of the formula is an obligation of this check, since it may be the clause that the witness falsifies. Hence, the check becomes harder as the solver learns more clauses. In practice, state-of-the-art techniques learn PR clauses only during preprocessing, before CDCL starts learning.

In this talk, we introduce Scaffolded DPR (SDPR), a clausal proof system that generalizes DPR, the proof system whose steps add PR clauses and delete clauses. SDPR divides the clauses into core clauses, which are both premises and obligations of the check, and scaffold clauses, which are only premises. Hence, the scaffold clauses, in particular the clauses learned by CDCL, strengthen the check rather than making it harder. In addition, SDPR maintains a set of repair literals. These allow deleting core clauses with a witness, as simplifications such as variable elimination do, while every scaffold clause remains. We show that SDPR is sound, and that SDPR and DPR polynomially simulate each other. Based on SDPR, we present InPRocess, an inprocessing technique that learns PR clauses during the search, alongside the solver’s other simplification techniques. We implemented InPRocess in CaDiCaL and evaluated it on the main track of the SAT Competition 2026. InPRocess outperforms both CaDiCaL and its preprocessing counterpart PReLearn: it solves more formulas, including formulas that neither of them solves.