4 papers
Probabilistic and Causal Satisfiability: Constraining the Model
Markus Bläser, Julian Dörfler, Maciej LiÅkiewicz +1
We study the complexity of satisfiability problems in probabilistic and causal reasoning. Given random variables over finite domains, the basic terms are probabil…
From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
Julian Dörfler, Benito van der Zander, Markus Bläser +1
The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of reasoning: probabilistic (i.e. purely observational), interventional, and counterfactual, that reflect the…
The Existential Theory of the Reals with Summation Operators
Markus Bläser, Julian Dörfler, Maciej Liskiewicz +1
To characterize the computational complexity of satisfiability problems for probabilistic and causal reasoning within the Pearl's Causal Hierarchy, arXiv:2305.09508 [cs.AI] introdu…
On the Complexity of Identification in Linear Structural Causal Models
Julian Dörfler, Benito van der Zander, Markus Bläser +1
Learning the unknown causal parameters of a linear structural causal model is a fundamental task in causal analysis. The task, known as the problem of identification, asks to estim…