# On the Complexity of Identification in Linear Structural Causal Models

arXiv: https://arxiv.org/abs/2407.12528 · HTML: https://mlsanity.com/paper/2407.12528/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 40 references that are in the map.
- First posted on arXiv 17 Jul 2024.

## Builds on (most cited first, 6 of 6)

- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Identification and Model Testing in Linear Structural Equation Models using Auxiliary Variables](https://mlsanity.com/paper/1612.03451/) (2016)
- [Efficient Identification in Linear Structural Causal Models with Instrumental Cutsets](https://mlsanity.com/paper/1910.13493/) (2019)
- [Incorporating Knowledge into Structural Equation Models using Auxiliary Variables](https://mlsanity.com/paper/1511.02995/) (2015)
- [Identification in Tree-shaped Linear Structural Causal Models](https://mlsanity.com/paper/2203.01852/) (2022)
- [Identification for Tree-shaped Structural Causal Models in Polynomial Time](https://mlsanity.com/paper/2311.14058/) (2023)

## Built on by (most cited first, 1 of 1)

- [Efficient Symbolic Computations for Identifying Causal Effects](https://mlsanity.com/paper/2604.20516/) (2026)

## Abstract (arXiv)

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 estimate the parameters of the model from a combination of assumptions on the graphical structure of the model and observational data, represented as a non-causal covariance matrix. In this paper, we give a new sound and complete algorithm for generic identification which runs in polynomial space. By standard simulation results, this algorithm has exponential running time which vastly improves the state-of-the-art double exponential time method using a Gr"obner basis approach. The paper also presents evidence that parameter identification is computationally hard in general. In particular, we prove, that the task asking whether, for a given feasible correlation matrix, there are exactly one or two or more parameter sets explaining the observed matrix, is hard for forall R, the co-class of the existential theory of the reals. In particular, this problem is coNP-hard. To our best knowledge, this is the first hardness result for some notion of identifiability.