7 citations · 8 across the 7 of their papers we have counts for
7 papers
On Proof Systems for #QBF
Sravanthi Chede, Leroy Chew, Vaibhav Krishan +1
For a quantified Boolean formula (QBF), the problem of computing the number of winning strategies is known as the #QBF problem. This problem is considered harder than the analogous…
Reintroducing the Second Player in EPR
Leroy Chew, Mikoláš Janota, Miroslav Olšák +1
We present a PSPACE-complete fragment of first order logic we call QEALM (QBF-like EPR by Alternating Level-ordered Miniscoping). Unlike other well-known fragments it is closer to…
Towards Uniform Certification in QBF
Leroy Chew, Friedrich Slivovsky
We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates cl…
Avoiding Monochromatic Rectangles Using Shift Patterns
Zhenjun Liu, Leroy Chew, Marijn Heule
Ramsey Theory deals with avoiding certain patterns. When constructing an instance that avoids one pattern, it is observed that other patterns emerge. For example, repetition emerge…
Feasible Interpolation for QBF Resolution Calculi
Olaf Beyersdorff, Leroy Chew, Meena Mahajan +1
In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. In this paper we establish the feasible interpolation techni…
Lifting QBF Resolution Calculi to DQBF
Olaf Beyersdorff, Leroy Chew, Renate Schmidt +1
We examine the existing Resolution systems for quantified Boolean formulas (QBF) and answer the question which of these calculi can be lifted to the more powerful Dependency QBFs (…
Tableau vs. Sequent Calculi for Minimal Entailment
Olaf Beyersdorff, Leroy Chew
In this paper we compare two proof systems for minimal entailment: a tableau system OTAB and a sequent calculus MLK, both developed by Olivetti (1992). Our main result shows that O…