5 citations · 7 across the 24 of their papers we have counts for
3 papers · 1 filter
Backdoors for Quantified Boolean Formulas
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
The quantified Boolean formula problem (QBF) is a well-known PSpace-complete problem with rich expressive power, and is generally viewed as the SAT analogue for PSpace. Given that…
Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas +1
We study a model of constraint satisfaction problems geared towards instances with few variables but with domain of unbounded size (udCSP). Our model is inspired by recent work on…
Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms?
Victor Lagerkvist, Magnus Wahlström
We study the complexity of SAT() problems for potentially infinite languages closed under variable negation (sign-symmetric languages). Via an algebraic connection, this red…