5 citations · 7 across the 5 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2022★ 1 cited
QBF Merge Resolution is powerful but unnatural
Meena Mahajan, Gaurav Sood
The Merge Resolution proof system (M-Res) for QBFs, proposed by Beyersdorff et al. in 2019, explicitly builds partial strategies inside refutations. The original motivation for thi…
cs.CC2020★ 1 cited
Hard QBFs for Merge Resolution
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan +2
We prove the first genuine QBF proof size lower bounds for the proof system Merge Resolution (MRes [Olaf Beyersdorff et al., 2020]), a refutational proof system for prenex quantifi…
cs.CC2020★ 5 cited
MaxSAT Resolution and Subcube Sums
Yuval Filmus, Meena Mahajan, Gaurav Sood +1
We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weaken…