Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy

• URL: http://arxiv.org/abs/2511.08091v1
• Date: Wed, 12 Nov 2025 01:39:08 GMT
• Title: Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
• Authors: Robert Ganian, Marlene Gründel, Simon Wietheger,
• Abstract summary: Pearl's Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements.<n>We revisit this challenge through the lens of parameterized complexity and identify the first gateways to tractability.
• Score: 16.72973567404685
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pearl's Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formulas is computationally intractable in almost all classical settings. We revisit this challenge through the lens of parameterized complexity and identify the first gateways to tractability. Our results include fixed-parameter and XP-algorithms for satisfiability in key probabilistic and counterfactual fragments, using parameters such as primal treewidth and the number of variables, together with matching hardness results that map the limits of tractability. Technically, we depart from the dynamic programming paradigm typically employed for treewidth-based algorithms and instead exploit structural characterizations of well-formed causal models, providing a new algorithmic toolkit for causal reasoning.

Related papers

• Addressing prior dependence in hierarchical Bayesian modeling for PTA data analysis I: Methodology and implementation [0.0]
  Complex inference tasks, such as those encountered in Pulsar Timing Array (PTA) data analysis, rely on Bayesian frameworks.<n>The high-dimensional parameter space and the strong interdependencies among astrophysical, pulsar noise, and nuisance parameters introduce significant challenges for efficient learning and robust inference.<n>We address these issues in the framework of hierarchical Bayesian modeling by introducing a re parameterization strategy.
  arXiv  Detail & Related papers  (2025-11-05T17:33:44Z)
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  We propose an end-to-end deep learning (DL) framework with low inference complexity for symbol-level precoding.<n>We show that the proposed framework captures substantial performance gains of optimal SLP, while achieving an approximately 80-times speedup over conventional methods.
  arXiv  Detail & Related papers  (2025-10-02T15:15:50Z)
• Probabilities of Causation and Root Cause Analysis with Quasi-Markovian Models [0.0]
  This paper introduces both algorithmic simplifications, significantly reducing the computational complexity of calculating tighter bounds for these probabilities.<n>It also introduces a novel methodological framework for Root Cause Analysis that systematically employs these causal metrics to rank entire causal paths.
  arXiv  Detail & Related papers  (2025-09-02T17:39:23Z)
• Identifying Causal Direction via Variational Bayesian Compression [6.928582707713723]
  A key principle is the algorithmic Markov condition, which postulates that the joint distribution, when factorized according to the causal direction, yields a more succinct codelength.<n>Previous approaches approximate these codelengths by relying on simple functions or Gaussian processes (GPs) with easily evaluable complexity.<n>We propose leveraging the variational Bayesian learning of neural networks as an interpretation of the codelengths.
  arXiv  Detail & Related papers  (2025-05-12T12:40:15Z)
• Structural Entropy Guided Probabilistic Coding [52.01765333755793]
  We propose a novel structural entropy-guided probabilistic coding model, named SEPC.<n>We incorporate the relationship between latent variables into the optimization by proposing a structural entropy regularization loss.<n> Experimental results across 12 natural language understanding tasks, including both classification and regression tasks, demonstrate the superior performance of SEPC.
  arXiv  Detail & Related papers  (2024-12-12T00:37:53Z)
• From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy [3.44747819522562]
  We show that languages allowing addition and marginalization yield NPPP, PSPACE, and NEXP-complete satisfiability problems, depending on the level of the PCH.<n>On the other hand, in the case of full languages, i.e. allowing addition, marginalization, and multiplication, we show that the satisfiability for the counterfactual level remains the same as for the probabilistic and causal levels.
  arXiv  Detail & Related papers  (2024-05-12T20:25:36Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  We compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. We evaluate their accuracy by providing credible intervals on the quality of the approximation.
  arXiv  Detail & Related papers  (2023-07-17T07:59:47Z)
• Compositional Probabilistic and Causal Inference using Tractable Circuit Models [20.07977560803858]
  We introduce md-vtrees, a novel structural formulation of (marginal) determinism in structured decomposable PCs. We derive the first polytime algorithms for causal inference queries such as backdoor adjustment on PCs.
  arXiv  Detail & Related papers  (2023-04-17T13:48:16Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• A Fast Non-parametric Approach for Causal Structure Learning in Polytrees [0.0]
  We develop DAG-FOCI, a fast algorithm for causal structure learning with no assumptions on the functional relationships and noise. We demonstrate the applicability of DAG-FOCI on real data from computational biology citesachs2005causal and illustrate the robustness of our methods to violations of assumptions.
  arXiv  Detail & Related papers  (2021-11-29T21:26:48Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Structural Causal Models Are (Solvable by) Credal Networks [70.45873402967297]
  Causal inferences can be obtained by standard algorithms for the updating of credal nets. This contribution should be regarded as a systematic approach to represent structural causal models by credal networks. Experiments show that approximate algorithms for credal networks can immediately be used to do causal inference in real-size problems.
  arXiv  Detail & Related papers  (2020-08-02T11:19:36Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.