Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
d-QBF with Few Existential Variables Revisited
Andreas Grigorjew, Michael Lampis
Quantified Boolean Formula (QBF) is a notoriously hard generalization of \textsc{SAT}, especially from the point of view of parameterized complexity, where the problem remains intr…
cs.CC2025
Circuits and Backdoors: Five Shades of the SETH
Michael Lampis
The Strong Exponential Time Hypothesis (SETH) is a standard assumption in (fine-grained) parameterized complexity and many tight lower bounds are based on it. We consider a number…