2 papers
cs.LO2026
Strong (D)QBF Dependency Schemes via Pure Paths with Applications to Proof Checking
Leroy Chew, Tomáš Peitl
Certification for Quantified Boolean Formulas (QBF) and Dependency Quantified Boolean Formulas (DQBF) is an ongoing challenge. Recent proof complexity work has shown that the major…
cs.LO2025
Better Extension Variables in DQBF via Independence
Leroy Chew, Tomáš Peitl
We show that extension variables in (D)QBF can be generalised by conditioning on universal assignments. The benefit of this is that the dependency sets of such conditioned extensio…