Pith. sign in

REVIEW 3 major objections 4 minor 40 references

Probabilistic and Causal Satisfiability: Constraining the Model

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Adding a causal graph to interventional satisfiability raises it from PSPACE-complete to NEXP-complete.

desk verdict Solid landscape-completing paper, but the written proof of the headline PSPACE-to-NEXP theorem has a fixable orientation bug in its graph construction. read the letter →

arxiv 2504.19944 v1 pith:3QSO3IXN submitted 2025-04-28 cs.CC cs.AIcs.LO

Markus Bläser , Julian Dörfler , Maciej Liśkiewicz , Benito van der Zander This is my paper · ORCID
classification cs.CCcs.AIcs.LO MSC 68Q1768Q25
keywords probabilisticsatisfiabilityPearl'scausalhierarchystructuralmodelsinterventionalreasoningcompactmarginalizationNEXP-completenessexistentialtheoryoftherealssmall-modelproperty
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how hard it is to decide whether a formula about probabilities, interventions, or counterfactuals has a satisfying causal model when the model is constrained. Its headline result is at the interventional level: if the causal graph is supplied as part of the input, satisfiability for basic or linear arithmetic with compact marginalization jumps from $\mathrm{PSPACE}$-complete to $\mathrm{NEXP}$-complete. The proof encodes satisfiability of Schönfinkel-Bernays sentences, a first-order fragment whose satisfiability is $\mathrm{NEXP}$-complete, into the interventional language; the graph edges enforce functional dependencies and compact sums express universal quantification. The paper also maps the remaining combinations of arithmetic, hierarchy level, graph constraint, and small-model constraint, showing which combinations change the complexity and which do not. The value is a near-complete computational landscape for problems that underlie causal inference, do-calculus verification, and probabilistic explanation.

What carries the argument

The load-bearing mechanism is the reduction from Schönfinkel-Bernays sentences, the effectively propositional fragment $\exists x\,\forall y\,\psi$, whose satisfiability is $\mathrm{NEXP}$-complete, into interventional-layer satisfiability over a prescribed DAG. For each relation $R_i$, the DAG declares its parents to be exactly its argument variables $Z_i^1,\ldots,Z_i^k$; a constraint of the form $\sum_{t_1,\ldots,t_k} P([T_1=t_1,\ldots,T_k=t_k,Z_i^1=t_1,\ldots,Z_i^k=t_k](R_i^j \neq R_i)) = 0$ forces copies of the same relation to agree on equal arguments. A compact summation $\sum_y P([y]\psi') = 2^n$ over the universal variables acts as a for-all quantifier. These ingredients let the graph replace the counterfactual machinery used in earlier hardness proofs, which is why the jump appears already at the interventional level with weak arithmetic.

What would settle it

Exhibit one satisfiable Schönfinkel-Bernays sentence whose translation in the proof of Theorem 7 is not satisfied by any Markovian SCM with the prescribed DAG, or is satisfied when the original sentence is not. Concretely, translate a small sentence such as $\exists x\,\forall y\,((R(x)\wedge R(y))\to x=y)$: if some assignment of exogenous variables with positive probability makes two copies of the relation $R$ disagree on equal declared arguments, then the graph edges alone have not forced the dependency the proof relies on, and the reduction fails.

Watch

Extended reading notes

Core claim

The central discovery is that adding the causal graph to the input changes the difficulty of satisfiability only at the interventional layer: the problems $\mathrm{Sat}^{\mathrm{base}\langle\Sigma\rangle}_{\mathrm{DAG},L_2}$ and $\mathrm{Sat}^{\mathrm{lin}\langle\Sigma\rangle}_{\mathrm{DAG},L_2}$ are $\mathrm{NEXP}$-complete, whereas the same languages without a fixed graph are $\mathrm{PSPACE}$-complete. The proof reduces satisfiability of Schönfinkel-Bernays sentences to these problems. Boolean variables become random variables, relation occurrences become random variables whose only declared graph parents are their arguments, and the compact marginalization operator expresses that a formula holds for all values of the universally quantified variables. The graph, together with the Markovian independence assumption, forces the relation variables to behave as deterministic functions of their arguments, so the reduction works even with basic or linear arithmetic.

Load-bearing premise

The proof that a prescribed DAG raises interventional satisfiability to $\mathrm{NEXP}$ assumes a Markovian causal model, meaning each observed variable has its own independent exogenous noise and no unobserved confounding is allowed. If shared hidden causes are allowed, the same DAG no longer pins down the functional dependencies among the observed variables, and the reduction's soundness collapses.

Editorial extensions

If this is right

  • Interventional satisfiability with a prescribed DAG is $\mathrm{NEXP}$-complete for basic and linear arithmetic, so deciding it in polynomial time would imply $\mathrm{P} = \mathrm{NEXP}$, and the corresponding validity problem is $\mathrm{co}$-$\mathrm{NEXP}$-complete.
  • Compact marginalization is what unlocks the jump: without the summation operator the small-model property keeps the problem in $\mathrm{NP}$, and with summation but no graph the same interventional layer is only $\mathrm{PSPACE}$-complete.
  • At the counterfactual layer and with polynomial arithmetic, the formula can encode the graph itself through exponential sums, so fixing the graph does not raise the complexity beyond the unconstrained case.
  • The small-model constraint does not tame interventional reasoning: with polynomial arithmetic, small-model interventional and counterfactual satisfiability remain $\mathrm{NEXP}$-complete because the deterministic mechanisms $F$ can still encode exponential information even when the support of the noise distribution is polynomially bounded.
  • For a fully specified Bayesian network, model checking a formula with polynomial arithmetic and summation lies in $\mathrm{P}^{\#\mathrm{P}}$, in sharp contrast to the $\mathrm{NEXP}$-complete satisfiability problem when only the graph is fixed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper: the same encoding suggests do-calculus verification—deciding whether an interventional rule holds for all SCMs with a given graph—could be inherently exponential when the query language uses compact sums, not just the satisfiability side.
  • Beyond the paper: because the $\mathrm{NEXP}$ reduction uses a fixed variable order and sparse parent sets, a natural test is whether polytrees or bounded-treewidth DAGs already give the jump; if they do, the hardness is carried by interventions plus summation rather than by graph width.
  • Beyond the paper: the authors conjecture that the missing cell $\mathrm{Sat}^{\mathrm{lin}\langle\Sigma\rangle}_{\mathrm{DAG},L_1}$ is $\exists\mathbb{R}^{\Sigma}$-complete. Adapting their ETR-INV encoding through the summation operator would settle that cell and complete the table.
  • Beyond the paper: the small-model results separate 'small support' from 'small mechanism' in causal models; polynomial support on noise does not bound the complexity of the functions $F$, which is the reason interventional queries stay exponentially hard.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the computational complexity of satisfiability and validity problems for probabilistic and causal languages over Pearl's Causal Hierarchy. It parameterizes the languages by arithmetic (basic, linear, polynomial), presence of a compact marginalization operator, and PCH level, and adds two new constraints: a specified causal DAG as part of the input, and a polynomial upper bound on model size. The headline results are: with a fixed DAG, Satbase⟨Σ⟩_{DAG,L2} and Satlin⟨Σ⟩_{DAG,L2} are NEXP-complete (Theorem 7), while Satpoly⟨Σ⟩_{DAG,L3} remains equivalent to the unconstrained succ-∃R-complete problem (Theorem 11); with small models, Satpoly⟨Σ⟩_{sm,L2} and Satpoly⟨Σ⟩_{sm,L3} are NEXP-complete (Theorem 14), and the probabilistic level drops to ∃RΣ via prior work [5]. The paper also proves that Bayesian-network model checking for polynomial arithmetic with summation is in P^#P and organizes the results into two landscape tables. The proofs are based mainly on reductions from Schönfinkel-Bernays satisfiability and on prior results by the same group.

Significance. If the proofs are completed, the paper makes a solid contribution. It identifies a genuine complexity jump from PSPACE to NEXP when the causal diagram is included in the input at the interventional layer, and it gives a nearly complete multi-parametric map across six arithmetic choices, three PCH levels, and two model constraints. The main hardness reductions are from scratch and are stated in a testable way, and the authors are candid about the sketch in Theorem 11 and about leaving Satlin⟨Σ⟩_{DAG,L1} open. These results would be of real interest to the probabilistic-logic and causality communities. However, as the manuscript currently stands, the central NEXP-completeness claim in Theorem 7 is not established because the graph construction in its proof is written in the wrong direction.

major comments (3)
  1. [§B.1, Proof of Theorem 7] The graph-construction step in the reduction from Schönfinkel–Bernays sentences is, as written, backwards. The text says: “We continue by ensuring that the values of X are not affected by the values of Y by making the Y the only predecessors of the X in G.” Under the causal-diagram definition in §2.3, an edge Y→X permits F_X to take Y as an argument; it does not forbid it. To make X independent of Y one must instead specify that no edge Y→X is present. As stated, the construction allows a model with F_X(Y)=Y and Y uniform: for the false sentence ∃x∀y(x=y), equation (7) is satisfied because P([Y=0](X=0))=P([Y=1](X=1))=1, while no single x works for both values of y. The subsequent soundness argument that “the values x of the variables X deterministically depend only on the values u of the exogenous variables” is therefore not justified. The proof should specify the intended graph (X with no incoming edges from Y) and should state explicitly that the DAG constraint is exact for absent edges, not merely a lower bound on the edge set.
  2. [§4.2, Theorem 11] The proof of Theorem 11 is not a proof as it stands. The encoding formula is displayed as ∑_v P([t_1,...,t_k] X_i ≠ [v\ x_i] X_i)=0 and then deferred with the remark that “this constraint uses a bit of notational sugar, explained in detail in the proof of Theorem 7.” The proof of Theorem 7 does not explain this notation or the encoding. The displayed expression mixes two different interventional contexts inside one primitive, and the counterfactual semantics of L3 permit such an expression only after a precise definition of the abbreviation (e.g., as a conjunction of two post-interventional formulas over the same exogenous variables). Since Theorem 11 is used for Proposition 6, Corollary 12, and the NEXP upper bound in Theorem 7, this missing derivation is load-bearing. Please provide a complete formal encoding into E_counterfact and prove the equivalence for each of the three arithmetic classes.
  3. [§4.1, Proposition 6] The proof of Proposition 6 appears to state the reduction directions backwards. It says “Since any probabilistic formula is a special case of a counterfactual one and Satpoly⟨Σ⟩_{L1} is succ-∃R-complete, we get Satpoly⟨Σ⟩_{DAG,L1} ≤_P Satpoly⟨Σ⟩_{L1}.” This would be the direction needed for membership only if DAG-constrained L1 formulas were a special case of unconstrained L1 formulas, which they are not; the special-case relation gives a reduction from DAG,L1 to DAG,L3, not to L1. Conversely, Proposition 2 gives Satpoly⟨Σ⟩_{L1} ≤_P Satpoly⟨Σ⟩_{DAG,L1}, which is the hardness direction, not the “opposite” relation named in the proof. The proposition may be true and the fix is straightforward (membership via DAG,L1 ≤_P DAG,L3 together with Theorem 11), but the proof as written should be corrected.
minor comments (4)
  1. [§2.3] The definition of “DAG G represents the graph structure” only says that every argument of a function appears as an incoming edge; it does not say that the edge set is exact. Since the proof of Theorem 7 repeatedly uses the phrase “exactly the edges,” please state the exact-parent convention explicitly.
  2. [§B.1, Proof of Lemma 5] The addition-encoding step says “the value should not be larger than P(X_k=0),” but the original ETR-INV equation is x_i+x_j=x_k, which is an equality. Please clarify how both the ≤ and ≥ directions are enforced, or correct the sentence.
  3. [Throughout] The fragment name is consistently written “Schönfinkel-Bernay” in the proof of Theorem 7; it should be “Schönfinkel-Bernays.”
  4. [§2.4] The class ∃RΣ is used without a definition; since it is introduced in the companion paper [5], a one-sentence definition or a precise pointer to the relevant definition would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the central hardness results reduce from external Schönfinkel-Bernays satisfiability, and the same-group citations are independent prior theorems, not renamed inputs.

full rationale

The paper's main new load-bearing claims, Theorems 7 and 14, are proven by explicit polynomial-time reductions from satisfiability of Schönfinkel-Bernays sentences, an external NEXP-complete problem. The reduction constructs DAG-constrained interventional formulas whose satisfying models are meant to witness the existential variables of the EPR sentence; this is a genuine reduction from an independent problem, not a restatement of the problem being defined. The membership directions for Theorem 7 and several entries of the landscape tables cite prior work by overlapping authors ([9], [5], [39]), but those are separate published theorems about unconstrained or differently constrained satisfiability problems and do not presuppose the results of this paper. They are parameter-free stated results with their own proofs, not fitted values or renamed conclusions of the present derivation. The paper also contains self-contained arguments for Proposition 2, Fact 3, Lemma 9, and Theorem 11's graph-encoding constraints. The skeptical concern raised about the 'Y are the only predecessors of the X' sentence in the proof of Theorem 7 is a potential soundness/correctness issue about whether the graph prevents X from depending on Y; it is not a circularity, because the reduction's output is not equivalent by construction to the target sentence. No step fits the categories of self-definition, fitted-input-called-prediction, uniqueness imported from authors, ansatz smuggled in via citation, or renaming a known result. The reliance on same-group citations is heavy but does not make the derivation circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The paper's claims rest on standard complexity-theoretic tools and domain assumptions about structural causal models; no free parameters or empirical inputs are used.

assumptions (5)
  • standard math Renegar's algorithm decides ETR in PSPACE, including formulas with exponentially many monomials but polynomially many variables.
    Invoked in Algorithm 2 of the proof of Theorem 14 to solve the constructed ETR formula in exponential time.
  • standard math Satisfiability of Schönfinkel-Bernays sentences is NEXP-complete, even for binary variables.
    Used as the source of NEXP-hardness in the proofs of Theorems 7 and 14.
  • domain assumption Any SCM over discrete endogenous variables is equivalent, for post-interventional probabilities, to an SCM with discrete finite exogenous variables (Zhang et al. 2022, [40]).
    Invoked in Section 2.2 to justify restricting exogenous variables to discrete finite domains throughout the paper.
  • domain assumption Graph-constrained models are assumed to be Markovian: exogenous arguments of different functions are independent (Section 2.3).
    Needed for the graph structure to faithfully represent conditional dependencies, e.g., in the proof of Theorem 7 where incoming edges force functional dependence on parents only.
  • domain assumption For small-model problems, model size is measured by the support of P(U), the exogenous variables, and Fact 3 shows this is equivalent to support of P(X) for probabilistic formulas only in semi-Markovian models.
    Definition 1 and Facts 3 and 4; this choice drives the small-model results and fails for Markovian models.
invented entities (1)
  • complexity class ∃RΣ independent evidence
    purpose: Classifies Satpoly⟨Σ⟩_{sm,L1}, the small-model probabilistic satisfiability problem with polynomial arithmetic and compact summation.
    Defined in prior work by the same group [5]; shown to satisfy ∃R∪NPPP⊆∃RΣ⊆PSPACE and to be complete for Satpoly⟨Σ⟩_{sm,L1}. It is a formal definition, not an empirical entity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Probabilistic and Causal Satisfiability: Constraining the Model." pith.science (2026). https://pith.science/paper/3QSO3IXN

@misc{pith2026250419944,
  author       = {Pith},
  title        = {Pith review of: Probabilistic and Causal Satisfiability: Constraining the Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3QSO3IXN}},
  note         = {Machine review of arXiv:2504.19944}
}
abstract

We study the complexity of satisfiability problems in probabilistic and causal reasoning. Given random variables $X_1, X_2,\ldots$ over finite domains, the basic terms are probabilities of propositional formulas over atomic events $X_i = x_i$, such as $P(X_1 = x_1)$ or $P(X_1 = x_1 \vee X_2 = x_2)$. The basic terms can be combined using addition (yielding linear terms) or multiplication (polynomial terms). The probabilistic satisfiability problem asks whether a joint probability distribution satisfies a Boolean combination of (in)equalities over such terms. Fagin et al. (1990) showed that for basic and linear terms, this problem is NP-complete, making it no harder than Boolean satisfiability, while Moss\'e et al. (2022) proved that for polynomial terms, it is complete for the existential theory of the reals. Pearl's Causal Hierarchy (PCH) extends the probabilistic setting with interventional and counterfactual reasoning, enriching the expressiveness of languages. However, Moss\'e et al. (2022) found that satisfiability complexity remains unchanged. Van der Zander et al. (2023) showed that introducing a marginalization operator to languages induces a significant increase in complexity. We extend this line of work by adding two new dimensions to the problem by constraining the models. First, we fix the graph structure of the underlying structural causal model, motivated by settings like Pearl's do-calculus, and give a nearly complete landscape across different arithmetics and PCH levels. Second, we study small models. While earlier work showed that satisfiable instances admit polynomial-size models, this is no longer guaranteed with compact marginalization. We characterize the complexities of satisfiability under small-model constraints across different settings.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 33 canonical work pages

  1. [5]

    a ser, Julian D \

    Markus Bl \" a ser, Julian D \" o rfler, Maciej Li \' s kiewicz, and Benito van der Zander. The existential theory of the reals with summation operators. In 35th Int. Symposium on Algorithms and Computation, ISAAC 2024 , volume 322 of LIPIcs, pages 13:1--13:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

    work page 2024

  2. [9]

    o rfler, Benito van der Zander, Markus Bl \

    Julian D \" o rfler, Benito van der Zander, Markus Bl \" a ser, and Maciej Li \' s kiewicz. From probability to counterfactuals: the increasing complexity of satisfiability in Pearl’s Causal Hierarchy . In International Conference on Learning Representations ( ICLR ) . PMLR, to appear, 2025. Available as ArXiv TR 2405.07373

    arXiv 2025

  3. [39]

    The hardness of reasoning about probabilities and causality

    Benito van der Zander, Markus Bl\" a ser, and Maciej Li\' s kiewicz. The hardness of reasoning about probabilities and causality. In Proc. Joint Conference on Artificial Intelligence (IJCAI 2023), 2023

    work page 2023

  4. [1]

    The art gallery problem is R -complete

    Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is R -complete. In Proc. of the 50th ACM SIGACT Symposium on Theory of Computing, pages 65--73, 2018

    work page 2018

  5. [2]

    NEXP -completeness and universal hardness results for justification logic

    Antonis Achilleos. NEXP -completeness and universal hardness results for justification logic. In International Computer Science Symposium in Russia, pages 27--52. Springer, 2015

    work page 2015

  6. [3]

    Computational complexity: a modern approach

    Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009

    2009

  7. [4]

    Correa, Duligur Ibeling, and Thomas Icard

    Elias Bareinboim, Juan D. Correa, Duligur Ibeling, and Thomas Icard. On Pearl’s Hierarchy and the Foundations of Causal Inference, pages 507--556. Association for Computing Machinery, New York, NY, USA, 2022

    work page 2022

  8. [6]

    Some algebraic and geometric computations in PSPACE

    John Canny. Some algebraic and geometric computations in PSPACE . In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 460--467. ACM, 1988

    work page 1988

Show all 40 references
  1. [7]

    The computational complexity of probabilistic inference using B ayesian belief networks

    Gregory F Cooper. The computational complexity of probabilistic inference using B ayesian belief networks. Artificial intelligence, 42 0 (2-3): 0 393--405, 1990

    1990

  2. [8]

    Approximating probabilistic inference in Bayesian belief networks is NP -hard

    Paul Dagum and Michael Luby. Approximating probabilistic inference in Bayesian belief networks is NP -hard. Artificial Intelligence, 60 0 (1): 0 141--153, 1993

    1993

  3. [10]

    Structure learning in graphical modeling

    Mathias Drton and Marloes H Maathuis. Structure learning in graphical modeling. Annual Review of Statistics and Its Application, 4: 0 365--393, 2017

    2017

  4. [11]

    Smoothing the gap between NP and ER

    Jeff Erickson, Ivor Van Der Hoog, and Tillmann Miltzow. Smoothing the gap between NP and ER . SIAM Journal on Computing, 53: 0 FOCS20--102 -- FOCS20--138, 2024

    2024

  5. [12]

    A logic for reasoning about probabilities

    Ronald Fagin, Joseph Y Halpern, and Nimrod Megiddo. A logic for reasoning about probabilities. Information and computation, 87 0 (1-2): 0 78--128, 1990

    1990

  6. [13]

    Design of experiments

    Ronald Aylmer Fisher. Design of experiments. British Medical Journal, 1 0 (3923): 0 554, 1936

    1936

  7. [14]

    Review of causal discovery methods based on graphical models

    Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in genetics, 10: 0 524, 2019

    2019

  8. [15]

    Solving systems of polynomial inequalities in subexponential time

    Dima Grigoriev and Nicolai Vorobjov. Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput., 5 0 (1/2): 0 37--64, 1988

    1988

  9. [16]

    Probabilistic reasoning across the causal hierarchy

    Duligur Ibeling and Thomas Icard. Probabilistic reasoning across the causal hierarchy. In The 34th AAAI Conference on Artificial Intelligence, AAAI 2020 , pages 10170--10177. AAAI Press, 2020

    2020

  10. [17]

    Probing the quantitative–qualitative divide in probabilistic reasoning

    Duligur Ibeling, Thomas Icard, Krzysztof Mierzewski, and Milan Mossé. Probing the quantitative–qualitative divide in probabilistic reasoning. Annals of Pure and Applied Logic, 175 0 (9): 0 103339, 2024 a

    2024

  11. [18]

    On probabilistic and causal reasoning with summation operators

    Duligur Ibeling, Thomas Icard, and Milan Moss \'e . On probabilistic and causal reasoning with summation operators. Journal of Logic and Computation, page exae068, 2024 b

    2024

  12. [19]

    Probabilistic graphical models: principles and techniques

    Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009

    2009

  13. [20]

    Harry R. Lewis. Complexity results for classes of quantificational formulas. Journal of Computer and System Sciences, 21 0 (3): 0 317 -- 353, 1980

    1980

  14. [21]

    Improving causal discovery by optimal Bayesian network learning

    Ni Y Lu, Kun Zhang, and Changhe Yuan. Improving causal discovery by optimal Bayesian network learning. In Proc. of the AAAI Conference on Artificial Intelligence , volume 35(10), pages 8741--8748, 2021

    2021

  15. [22]

    Methods for causal inference from gene perturbation experiments and validation

    Nicolai Meinshausen, Alain Hauser, Joris M Mooij, Jonas Peters, Philip Versteeg, and Peter B \"u hlmann. Methods for causal inference from gene perturbation experiments and validation. Proceedings of the National Academy of Sciences, 113 0 (27): 0 7361--7368, 2016

    2016

  16. [23]

    Is causal reasoning harder than probabilistic reasoning? The Review of Symbolic Logic, pages 1--26, 2022

    Milan Moss \'e , Duligur Ibeling, and Thomas Icard. Is causal reasoning harder than probabilistic reasoning? The Review of Symbolic Logic, pages 1--26, 2022

    2022

  17. [24]

    Reliable causal discovery with improved exact search and weaker assumptions

    Ignavier Ng, Yujia Zheng, Jiji Zhang, and Kun Zhang. Reliable causal discovery with improved exact search and weaker assumptions. Advances in Neural Information Processing Systems, NeurIPS , 34: 0 20308--20320, 2021

    2021

  18. [25]

    Probabilistic logic

    Nils J Nilsson. Probabilistic logic. Artificial Intelligence , 28 0 (1): 0 71--87, 1986

    1986

  19. [26]

    Complexity results and approximation strategies for MAP explanations

    James D Park and Adnan Darwiche. Complexity results and approximation strategies for MAP explanations. Journal of Artificial Intelligence Research, 21: 0 101--133, 2004

    2004

  20. [27]

    Probabilistic reasoning in intelligent systems: networks of plausible inference

    Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 1988

    1988

  21. [28]

    Causal diagrams for empirical research

    Judea Pearl. Causal diagrams for empirical research. Biometrika, 82 0 (4): 0 669--688, 1995

    1995

  22. [29]

    Causality

    Judea Pearl. Causality. Cambridge University Press, 2009. ISBN 0-521-77362-8

    2009

  23. [30]

    The book of why: the new science of cause and effect

    Judea Pearl and Dana Mackenzie. The book of why: the new science of cause and effect. Basic books, 2018

    2018

  24. [31]

    Beware of the simulated dag! causal discovery benchmarks may be easy to game

    Alexander Reisach, Christof Seiler, and Sebastian Weichwald. Beware of the simulated dag! causal discovery benchmarks may be easy to game. Advances in Neural Information Processing Systems, NeurIPS , 34: 0 27772--27784, 2021

    2021

  25. [32]

    A scale-invariant sorting criterion to find a causal order in additive noise models

    Alexander Reisach, Myriam Tami, Christof Seiler, Antoine Chambaz, and Sebastian Weichwald. A scale-invariant sorting criterion to find a causal order in additive noise models. Advances in Neural Information Processing Systems, NeurIPS , 36: 0 785--807, 2023

    2023

  26. [33]

    On the computational complexity and geometry of the first-order theory of the reals

    James Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals . Journal of symbolic computation, 13 0 (3...

    1992

  27. [34]

    a us Kleindessner, Chris Russell, Dominik Janzing, Bernhard Sch \

    Paul Rolland, Volkan Cevher, Matth \"a us Kleindessner, Chris Russell, Dominik Janzing, Bernhard Sch \"o lkopf, and Francesco Locatello. Score matching enables causal discovery of nonlinear additive noise models. In International Conference on Machine Learning, ICLM , pages 18...

    2022

  28. [35]

    On the hardness of approximate reasoning

    Dan Roth. On the hardness of approximate reasoning. Artificial Intelligence, 82 0 (1-2): 0 273--302, 1996

    1996

  29. [36]

    Complexity of some geometric and topological problems

    Marcus Schaefer. Complexity of some geometric and topological problems. In International Symposium on Graph Drawing, pages 334--344. Springer, 2009

    2009

  30. [37]

    Complete identification methods for the causal hierarchy

    Ilya Shpitser and Judea Pearl. Complete identification methods for the causal hierarchy. Journal of Machine Learning Research, 9 0 (Sep): 0 1941--1979, 2008

    1941

  31. [38]

    Causal structure learning: A combinatorial perspective

    Chandler Squires and Caroline Uhler. Causal structure learning: A combinatorial perspective. Foundations of Computational Mathematics, pages 1--35, 2022

    2022

  32. [40]

    Partial counterfactual identification from observational and experimental data

    Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data. In International Conference on Machine Learning, pages 26548--26558. PMLR, 2022

    2022

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.