@inproceedings{
d{\"o}rfler2024on,
title={On the Complexity of Identification in Linear Structural Causal Models},
author={Julian D{\"o}rfler and Benito van der Zander and Markus Bl{\"a}ser and Maciej Liskiewicz},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=bNDwOoxj6W}
}
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 a standard simulation 
result, namely $\mathsf{PSPACE} \subseteq \mathsf{EXP}$,
this algorithm has exponential running time which vastly improves 
the state-of-the-art double exponential time method using a Gröbner 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 \mathbb{R}$, the co-class of the existential theory 
of the reals. In particular, this problem is $\mathsf{coNP}$-hard.
To our best knowledge, this is the first hardness result for some notion 
of identifiability.
On the Complexity of Identification in Linear Structural Causal Models
Julian Dörfler Benito van der Zander Markus Bläser Maciej Liskiewicz