6 citations · 12 across the 10 of their papers we have counts for
13 papers
The Complexity of Games with Randomised Control
Sarvin Bahmani, Rasmus Ibsen-Jensen, Soumyajit Paul +5
We study the complexity of solving two-player infinite duration games played on a fixed finite graph, where the control of a node is not predetermined but rather assigned randomly.…
Model Counting for Dependency Quantified Boolean Formulas
Long-Hin Fung, Che Cheng, Jie-Hong Roland Jiang +2
Dependency Quantified Boolean Formulas (DQBF) generalize QBF by explicitly specifying which universal variables each existential variable depends on, instead of relying on a linear…
Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
Leroy Chew, Alexis de Colnet, Friedrich Slivovsky +1
Parity reasoning is challenging for Conflict-Driven Clause Learning (CDCL) SAT solvers. This has been observed even for simple formulas encoding two contradictory parity constraint…
Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF
Johannes K. Fichte, Robert Ganian, Markus Hecher +2
The QSAT problem, which asks to evaluate a quantified Boolean formula (QBF), is of fundamental interest in approximation, counting, decision, and probabilistic complexity and is al…
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…
Engineering an Efficient Boolean Functional Synthesis Engine
Priyanka Golia, Friedrich Slivovsky, Subhajit Roy +1
Given a Boolean specification between a set of inputs and outputs, the problem of Boolean functional synthesis is to synthesise each output as a function of inputs such that the sp…