Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with dependency schemes:
TR16-028 | 29th February 2016
Olaf Beyersdorff, Joshua Blinkhorn

Dependency Schemes in QBF Calculi:Semantics and Soundness

Revisions: 1

We study the parametrization of QBF resolution calculi by dependency schemes. One of the main problems in this area is to understand for which dependency schemes the resulting calculi are sound. Towards this end we propose a semantic framework for variable independence based on `exhibition' by QBF models, and use ... more >>>

TR20-036 | 9th March 2020
Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl

Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths

We suggest a general framework to study dependency schemes for dependency quantified Boolean formulas (DQBF). As our main contribution, we exhibit a new tautology-free DQBF dependency scheme that generalises the reflexive resolution path dependency scheme. We establish soundness of the tautology-free scheme, implying that it can be used in any ... more >>>

TR20-159 | 9th October 2020
Leroy Chew, Marijn Heule

Relating existing powerful proof systems for QBF

We advance the theory of QBF proof systems by showing the first simulation of the universal checking format QRAT by a theory-friendly system. We show that the sequent system G fully p-simulates QRAT, including the Extended Universal Reduction (EUR) rule which was recently used to show QRAT does not ... more >>>

ISSN 1433-8092 | Imprint