On the Complexity of Identification in Linear Structural Causal Models
Authors: Julian Dörfler
Benito van der Zander
Markus Bläser
Maciej Liskiewicz
Venue: NeurIPS 2024 poster (2024)
Keywords: causal inference
structural causal models
structural equational models
generic identifiability
existential theory over the reals
Primary area: causal_inference
TL;DR: We prove a PSPACE upper bound for deciding generic identifiability and give the first hardness result for variants of identification.

Abstract: 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* Saarland University
Benito van der Zander" University of Lübeck
Markus Bläser' Saarland University
Maciej Liskiewiez University of Lübeck
Abstract
Learning the unknown causal parameters of a linear structural causal model is a fundamental task in causal analysis. The task, known the problem of iden- tification, asks to estimate the parameters of the model from a combination assumptions the graphical structure of the model and observational data, repre- sented 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 PSPACE C EXP, this algorithm has expo- nential running time which vastly improves the state-of-the-an double exponential time method using a Gröbner basis approach. The paper also presents evidence that parameter identification computationally hard in general. In particular, we prove, that the task asking whether, for given feasible correlation matrix, there are exactly one or two or more parameter sets explaining the observed matrix, is hard for VR, the co-class of the existential theory of the reals. In particular, this problem cord- To our best knowledge, this the first hardness result for some notion of identifiability.
1 Introduction
Recognizing and predicting the causal effects and distinguishing them from purely statistical corre- lations is an important task of empirical sciences. For example, identifying the causes of disease and health outcomes of great significance in developing new disease prevention and treatment strate- gies. A common approach for establishing causal effects is through randomized controlled trials (Fisher, (20) called the gold standard of experimentation which, however, requires physical in- tervention in the examined system. Therefore, in many practical applications, experimentation not always possible due to cost, ethical constraints, or technical feasibility. E.g., to learn the effects of radiation human health one cannol conduct interventional studies involving human participants. In such cases, a researcher may use an alternative approach and establish cause-effect relationships by combining existing observed data with the knowledge of the structure of the system under study. This is called the problem of identification in causal inference (Pearl, [2] and the approach is commonly used in various fields, including modern ML.
A key ingredient of this framework is the way the underlying structure models the true mechanism behind the system. In general, this is done using structural causal models (SCMs) 32 3 In this work, we focus on the problem of identification
linear SCMs, known also as structural equation models (SEMs) 7 [8] They represent the causal relationships between observed random variables
'Equal contribution as first authors.
Equal contribution as last authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

3
A
X2,3
Figure I: An IV example.
assuming that each variable X,, with i = 1,...,, 7 is linearly dependent on the remaining variables and an unobserved error term E; of normal distribution with zero mean: Xj = Ai, + Ej. The model implies the existence of some covariance matrix S = (wx,) between the error terms. In this paper, we consider mainly recursive models, i.e., we assume that, for all i > J. we have λi.j = 0, nonetheless we discuss how our methods can be extended to the general case.
Linear SCMs can be represented a graph with nodes {l..... nn corresponding to variables XX, and with directed and bidirected edges. A directed edge - j represents a linear influence ) + 0 of a parent node i on its child j. A bidirected edge j represents a correlation Wi,j # 0 between error terms & and Ej (cf. Figure D
Writing the coefficients of all directed edges as an adjacency matrix A = (Ar.)) and the coefficients of all bidirected edges as an adjacency matrix Q = (wi,g), the covariances Tijj between each pair of observed variables X; and Xj can be calculated as matrix Σ = (ox.)):
= - A1- - A)-1, -
(1)
where 1 is the identity matrix (21). Knowledge of the parameters A allows for the prediction of all causal effects in the system. The key task here is to learn A from the observed covariances E assuming f remains unknown. This leads to the formulation of the identification problem in linear SCMs as solving for the parameter A using equation (I. If the problem asks to find symbolic solutions involving only symbols oıj. we call the problem of symbolic identification. In the case when the parameter can be determined uniquely almost everywhere using Σ alone, we call the instance be generically identifiable (for formal definition, Sec. 2 If the goal is to find, for a given Σ of rational numbers. the numerical solutions, we call it the problem of numerical identification. In this paper, we study the computational complexity of both variants of the problem.
Previous Work. The identification in linear SCMs and its applications have been a subject of re- search interest for many decades, including the early work in econometrics and agricultural sciences 19 8). Currently, it seems, that one of the most challenging tasks in this field is providing efficient computational methods to find solutions, both for symbolic and for numeric variants, or providing evidence that the problems are computationally intractable.
42
The generic identification can be computed using standard algebraic tools for solving symbolic poly- nomial equations (T). Such an approach provides a sound and complete method, i.c., it is guarantced to identify all identifiable instances. However, common algorithms for solving such equations usu- ally use Gröbner basis computation, whose time complexity doubly exponential in the worst case (22]. So far, it has remained widely open whether the double exponential function is sharp upper bound on the computational complexity of the generic identifiability.
Most approaches to solving the problem in practice are based on instrumental variables, in which the causal direct effect is identified as a fraction of two covariances [1 8]. For example, in the linear
A1,2 01.2" The variable X, is then called an instrumental variable (IV). This method is sound but not complete, that is, when it identifies a parameter, then it is always correct. However, when the method fails due to a missing IV, then the parameter might still be identified by other means. This approach has inspired intensive research aimed at providing computational methods that may not be complete but enable efficient algorithms and identify significantly large number of cases.
model shown in Figure 1 one can calculate first \1,2 = 01,2 and then 22,3 A1,2Za
aus
Conditional IVs (cIVs) are one of the most natural extensions of simple IVs g The correspond- ing identification method is based on an efficient, polynomial time algorithm for finding conditional IV' (38] More complex criteria and methods proposed in the literature, which are also accompanied by polynomial time algorithms, involve instrumental sets (IS) [10] half-treks (HTC) 21). instrumen- tal cutsets (ICs) (28), auxiliary instrumental variables (alVs) [5]. The generalized HTC (gHTC)
1 40 and auxiliary variables (AVS) [3] [4 can be implemented in polynomial time provided

---

gs, sc1S 11
37
gAVS 14
Complete Methods
double-Eii EXP
IV 41
is. HTC, AVS, gHTC 10
21
14
13
40
IC 28
ACID 29
Gröbner 22
PSPACE
this paper
cIV, alv 15
cAV 14
Treell) 33 24
Figure 2: Methods for generic identification in linear SCMs. An arrow from methods A B means that subsume all methods A, i.e., any instance that can be identified by any of methods A can be there exist polynomial-time
identified by method B and this inclusion is proper. Green boxes algorithms to apply the method, red box means no such algorithm is known or the method has been proven be NP-hard. The blue box includes the complete methods.
that the number of incoming edges to each node in the causal graph is bounded. The methods based on generalized IS (gIS), simplified version of the criterion (scIS), and generalized AVS (gAVS)
appeared to be computationally intractable [O, 9 I 37 14 The auxiliary cutsets (ACID) algo- rithm [29] subsumes all the above methods in the sense that it covers all the instances identified by them. Recently [39 24 provide the TreeID algorithm for identification in tree-shaped linear models. TreeID is incomparable since it is complete for the subclass of reke-like SCMs. However, TreeID does not work for general SCMs, which is the focus of our work. Figure summarizes these results.
Numerical parameter identification, known in the literature as the estimation of the parameters of structural equation models, has been the subject of a considerable amount of research, which has resulted in significant progress in theoretical understanding and development of estimation methods 26 12 30 25). Currently, in practical applications (e.g. in econometries, psychometrics, or biometrics), methods based maximum likelihood (ML) or generalized least squares estimator (GLS) are commonly used to find model parameters. However, despite the great importance of this problem and considerable effort in method development, the computational complexity of the parameter estimation problem remains unexplored. In our work, we provide, to our knowledge, the first hardness result for very basic variant of the SEM parameter estimation problem, which call numerical identification.
Our Contribution. We improve significantly the best-known upper bound the computational complexity for generic identification and provide evidence that parameter identification is computa- tionally hard in general. In more detail, our contributions
follows:
We provide polynomial space algorithm for sound and complete generic parameter iden- tification linear models. This gives an exponential running time which vastly improves the state-of-the-art double exponential time method using Gröbner basis. In our approach, we formulate generic identifiability and universal quantifiers and then use Renegar's algorithm
formula over real variables with both existential
33
Our constructive technique allows us to prove an MvR (and VEIR upper bound on generic identifiability, for the well-studied complexity class .vR (see Sec. 2.2 for definitions). It is an intermediate class between NP and PSPACE.
We prove that numerical identification is hard for the complexity class VRR. In particular, the problem is coNP-hard. Our complexity characterization is quite precise since we show a (promise) VR upper bound for numerical identification. To the best of our knowledge, this is the first hardness result for some notion of identifiability.
On the other hand, we show that numerical identifiability can be decided in polynomial space.
If an instance is non-identifiable, then an important task is to identify as many model pa- rameters as possible. We are particularly interested in identifying the parameters of specific edges in the graph representing the linear model. In the paper, we obtain, for "edge iden- tifiability", the same results as for the common identifiability problem. Since these proofs are essentially the same, they can be found in Appendix

---

2 Preliminaries
2.1 The Problems of Identification in Linear Causal Models
mixed graph is a triple G = BB where V == [n is a finite set of nodes and D S V x V and B S (2) are two sets of directed and bidirected edges, respectively. Let RP be the set of matrices A = (Aa,) ) E R= with Az, iff i + is not in D and let PD(n) denote the cone of positive definite n x n matrices. Let PD(B) be the set of matrices f = (We,) E PD(n) with wij = 0f + j and ++ j not an edge in B. For now, we will only consider recursive models, iee. we assume that, for all i j. we have Ar be extended to general graphs allowing cycles). Thus, the directed graph (V, D) accompanied with the model is acyclic. We will assume w.l.o.g. that the nodes are topologically sorted, i.e., there are no edges i + with i j.
(in Sec. we will discuss how our methods can
Denote by (H, Σ) the multivariate normal distribution with mean μ E R" and covariance matrix E. The linear SCMs M(G) associated with G = (V. D, B) is the family of multivariate normal distributions No, (0, Σ) with Σ satisfying equation ( for A IR' and Ω E PD(B). A model in MMG) is specified in a natural way in terms of system of linear structural equations: Xj = Eiegu(s)
for j I,..., n, where pa(j) denote the parents of j in G. If (s1,...,6y, is a random vector with the multivariate normal distribution N (0, Σ) and A E RR,, then the random vector = (X1.... X,) is well defined as solution to the equation system and follows a centered multivariate normal distribution with covariance matrix (1 A)- T2 A)- (sce, e.g. (17).
For given (acyclic) mixed graph G DV B3. define the parametrization map
ΦG (A, - (1 - -
and let θ = RD x PD(B). We say that G' is globally identifiable if ΦG is injective on θ
be decided easily, see [17 Theorem 2). However, it is very strong prop- erty. For instance, as seen in the introduction, in Figure [ we can recover the parameter 22 as 013
Global identification
If 1,2 O, then the identification fails, the instance is not globally identifiable. But iden-
01.2"
tification fails only in the (very unlikely) case that 01.2 = This leads to the concept of generic identifiability:
Definition (Generic Identifiability, 21
The mixed graph G is said to be generically identifiable de is injective on the complement + of proper (i.e., strict) algebraic subset V C O.
Given matrices No E IR. and 24 E PD(B), the corresponding fiber is defined by
Fa(Ao, Un) ) = (A, @c(A, da (Ao, Ro), A E A R Ω PD(B))
A fiber contains all pairs of matrices that induce the same observed covariance matrix Σ. For Σ im éc, we also write Fo(Z) for the fiber belonging to E. We can phrase identifiability in terms of fibers:
. G is globally identifiable, if Fo(oo. = 1 for all Ao E R and Qo E PD(B).
is generically identifiable, if [ao 2o) = 1 for Zariski almost all Ao E R and
Po E PD(B).
Generic identifiability asks whether all parameters are almost always identifiable in the Zariski sense, that is, everywhere except for lower dimensional algebraic set. For generic identifiability, we only consider the parameters As,, since the parameters Wa,1 can be recovered from the >r and T, using [1] see also [16).
is also of interest to ask whether a single parameter Aı,j is almost always identifiable. For this, we consider the projection of the fiber on the single parameter, which we will also call an edge fiber:
Frd (Ao, S2) (Ars (A, E Fo Do)}.
(Above Ai, denotes the entry of in the position (i, j). that is, As.j.)
Definition 2. The parameter Xi. is generically edge identifiable, if F1 (Ao, = 1 for Zariski almost all No E RD and Qy PD(

---

Global and generic identifiability are properties of the given mixed graph. In this work, we also study identification as a property of the observed numerical data, i.., of the observed covariance matrix Σ.
Definition 3 (Numerical Identifiability). Given acyclic mixed graph G = DV B) and feasi- ble matrix E,, decide whether the parameters are uniquely identifiable, i... if Fo()) 1?
Note that this is promise problem. We assume that Es feasible, i.e., in the image of da. Therefore, we shall also study the feasibility problem: Given Σ, is it contained in im dc?
Similarly we can also define numerical edge identifiability; For given feasible Σ, test whether the edge fiber Σ belongs to has size 1 or >> 1.
2.2 The (Existential) Theory of the Reals
The existential theory of the reals (ETR) is the set of true sentences of the form
Fr ... Rr, ,(,
where is a quantifier-free Boolean formula over the basis {V. -} and a signature consisting of the constants 0 and 1, the functional symbols + and and the relational symbols S. and =. The sentence is interpreted over the real numbers in the standard way. The theory forms its own complexity class FIR which is defined the closure of ETR under polynomial-time many- one reductions. Many natural problems have been shown to be complete for ETR, for instance the computation of Nash equilibria (35), the famous art gallery problem [1) or training neural networks 51 just to mention few. See the recent compendium (34 for complete overview.
It turns out that one can simplify the form of an ETR-iistance. We can get rid of the relations < and < and it is sufficient to consider only Boolean conjunctions. More precisely, the following problem is ER-complete: Given polynomials P1 ........ Pm in variables .n,....Ins decide whether there is
g E R" such that
(E(
Pm)(E) = 0.
(3)
By Tseitin's 's trick, we can assume that all polynomials are of one of the forms
ab c, + b a- a a-
(4)
and all variables in each of the polynomials distinet. Note that all polynomials in have degree at most two. Therefore, this problem also called the feasibility problem of quadratic equations QUAD. For a proof, see e.g. 35
Universal Quantification. If, instead of considering existentially quantified true sentences, we consider universally quantified true sentences of the form
Ya VEn pf I.,),
(5)
where is again a quantifier-free Boolean formula, and form the closure under polynomial-time many-one reductions, obtain the complexity class VR. Using De Morgan's 's law, it is easy to the well-known fact that VR = co-3IR, i.c. it is the complement class of FIR.
It is also possible to alternate quantifiers, giving rise to whole hierarchy, comparable to the well- known polynomial time hierarchy, see [36]. We call the corresponding classes EVR, VEI,
Complexity of 3R and VR. It is easy to see that quantification over real variables can be used to simulate quantification over Boolean variables by adding the constraint æ(x - 1) 0. This way we can convert ASAT-formula ETR-formulas, proving the well-known containment NP S ER.
With his celebrated result about quantifier elimination, Renegar 33 proved that the truth of any sentence over the reals with constant amount of quantifier alternations is decidable in PSPACE. This in particular implies
NP C 3R C PSPACE
and coNP C YR C PSPACE.
(6)
While all these inclusions are believed to be strict, it is unknown for all of them.
5

---

Finding Another Solution
Numerical identification is a promise problem, i.., assume that the given input is feasible. Being a promise problem means that an algorithm for numerical identification should output the correct answer whenever the input is feasible. But it output anything when the input is not feasible. We give some further information about promise problems in Appendix [B for the reader's convenience.
For our hardness proof, we need to look instances of ETR or QUAD that are satisfiable. Of course, deciding whether satisfiable instance is satisfiable trivial task. So the task will be to decide whether the satisfiable instance has another solution. We call the corresponding promise problems ETR ++ and QUAD
It turns out that these promise problems are ElR-hard. Since QUAD++ is special case of ETR ++, suffices to prove this for QUAD+ Let y an extra variable. We will plant an extra solution
into the system
yyy 1) = 0
yr, 0
i= 1,
(8)
(y 1)p; = 0 Lemma 1. The system above has the following solutions:
j=1. j=1....,
(9)
1. y 1, 11
2. y 0, . _1.....
En, where & IR" is any solution to the original instance.
In particular, the system always hus solution. It has more than one solution iff the original QUAD- instance is satisfiable.
Proof. The first equation constrains to be {0, 1}-valued. If O, then the equations are trivially satisfied and 9 trivially satisfied and ( reduces to
reduces to the original instance (3). = I, then the equations are
In O. Note that in both cases we always get
different solutions since the y-value differs.
Using the transformation in the lemma above, we can map any QUAD-instance into QUAD++ instance and obtain
Corollary 1. ETR ++ *add QUAD are 3R-hard.
Hardness of Numerical Identifiability
This section is dedicated to proving: Theorem 2. Numerical identifiability is VR-hard.
The proof consists of building polynomial cittomill--meeeeeee reduction from the complement of QUAD to numerical identifiability, i.e., we construct an acyclic mixed graph G and a Σ E im Φo. such that the fiber FG(E) has size iff the given QUAD+*-instame
only one solution. For this, we use
the following characterization of fibers due to [16]:
Lemma 3. Ler G D. B) be an acyclic mixed graph, and let Σ im dG. The fiber Fo(E) is isomorphic to the set of matrices A E IR that solve the equation system
[(1 - A) E - =
+ j, i ++ B
(10)
We construct G follows: The directed edges form bipartite graph with edges going from the bottom layer to the top layer. Every node at the bottom layer has outdegree one. Moreover bidirected edges exist between all pairs of nodes, except for certain pairs of nodes of the top layer. See Figure (left-hand side) for an illustration.
This missing edge in Figure 3 corresponds to the equation
0 oij
Σ Joeisaet
Tbe Abeu
Joe by AaciiDbunt
(11)
in Lemma 3

---

missing
Aanui
Abmi.
Air
An,r
an
b1
Om
Figure 3: Left: A single missing edge on the top layer. Right: The gadget storing the value of each variable. Ai, corresponds to z;.
missing
missing
missing
missing
A1,r
Aaar
A
Aua
Av.
X
Figure 4: Left: Gadget for affine linear constraints. Right:
Gadget for multiplicative constraints.
Observation 4. All values that appear in (11) cannot appear in any other missing edge equation of missing edges the top layer. Parameters Jaz. can only appear an equation of missing edge that contains the node and another node h such that there is a directed edge from to h. However, (ag, 1) is the only such edge, since the nodes in the bottom layer only have outdegree one. The same is true for Jb Oag.be only appear in equation of missing edge h ++ h' if there are directed edges (ar, h) and (bg,h') By the same argument, ++ j is the only such missing edge. Furthermore oi can obviously only appear in this equation.
The above observation means that we can freely "program" the equations, that is, we can freely choose the o-values in each missing edge equation without interfering with any other missing edge equation.
We start with gadget with node in the top layer and nodes in the bottom layer connected to it. is used to store the value each variable of our ETR instance, Λ1, corresponds to ø1, X2, corresponds to 22, etc, Figure 3 (right-hand side) for illustration.
By assuming all polynomials in our QUAD++ -instance are of the forms 44) we need be able to encode products and affin linear forms. We start by showing how to encode an arbitrary affine linear constraint Σm= Okgdg
using a single additional node in the top layer, "connected" to
via a missing edge in Figure 4
Setting Tr, and Øe, = ar, 1 <ES n, makes 11 together with de, xe directly equivalent to ΣE= axT1 B.
Encoding product v. Fb ze requires two additional nodes and in the top layer, with missing bidirectional edges between them and r. Furthermore we introduce two nodes and j' in the bottom layer, connected to i and respectively, equations. The missing edge r
Figure 4 (right-hand side). This introduces three ++ enforces Av, = Aer by setting Cr.i = 01,1 = Gn,s' = O, and σe 0, for all (l,...,,) n) \ {c) (1). We i ++ j to further ensure Ay = Ay.; = An,r for which we set oi = or = =0, or = 1, and Jijy' -1 After having copied Acr twice, we finally able enforce the multiplication itself using the missing edge ++ j. We set or. = Grd = 0, Ja.j = 1, "b." 1, oe, = O, for all É E (I. {a}. and oe, for all f (I....,,. n (b). We need copy the parameter Aor twice to be able to "program" the equation corresponding to the missing edge r ++ j.
T,,"" 11, o.,
the missing edge
Proof of Theorem Let polynomials PI.... Pm variables . Tn be a QUAD ++ -instance with all polynomials being one of the forms in (4) Let the number of affine linear polynomials among Pt.... Pm be k. Then the graph G = DV, constructed above has == + n + k + 4(m k) 1 1 n + 4m 3k nodes. Using Observation 4 we see that the construction induces well-defined partial matrix Σ E T exe Every entry of Σ. not defined by the construction is set to
7

---

O if it is off- off-diagonal and if it is on the diagonal. Since all oij set in the construction are from {-1,0, 0,1, and off-diagonal, Σ strictly diagonally dominant by our choice of & and thus positive definite by the Gershgorin circle theorem [23]
Remains to prove E E im ΦG. Let & E IR.h be any solution with pı pz(E) =... =.. =m = 0. The existence of Ç is guaranteed by the promise of QUAD++. Create A E Rxxt follows: Ai. ç for i E f1...., n and X = X = &e whenever the vertices i, J.J are the vertices added by the construction due to a multiplication. All other entries of we have Σ = (,(A, for Ω = - (I-A)" A) - A). Furthermore Ω is positive definite due to Σ being positive definite and 52 PD(
Then I - A is invertible and
By Lemma 3 this implies that [Fa(E)) is precisely the number of solutions of our QUAD++ instance. So if the QUAD** ++ -instance is a ves-instance, that is, has more than one solution, then our constructed instance is not numerically identifiable. the QUAD -instance a no-instance, that is, has only one solution, then our constructed instance is numerically identifiable. So we have a reduction from the complement of QUAD+ The theorem now follows, since by Corollary QUAD++ is -R-h and the complement of an -ll- problem is V/R-hard.
Upper Bound for Numerical Identifiability
In this section, we show yR upper bound for numerical identifiability and thus, combined with Theorem2 2 prove an almos matching lower and upper bound. We start with the following lemma. The AIR part will be needed in the next section.
Lemma 5. Membership in PD(n) and (B can be expressed in ER and VR.
Proof. For the AR expression, use the fact that every real positive definite matrix A E Rax= has Cholesky decomposition = LL" where is a real lower triangular matrix with positive diagonal entries. We can thus express A E PD(n) as
e E Rax"
LL" A
(
A CONANN
:, 0).
(12)
(E(I.....)
jE(++ (.........))
We quantify over matrices and consider matrix equations in (12). But this can be easily rewritten as an ETR-iintaacee by quantifying over all entries of the matrix and having one individual equation for each entry of the matrix equation.
For the VR expression, we directly use the definition of positive definite matrices to express A E PD(n) as
Vx E R x
x Ax O.
(13)
For membership A E PD(B). in both ER and VR, we add the constraint AGGIEBRiTS Ars = 0 to and (13 respectively.
We remind the reader that numerical identifiability is promise problem with the promise that the input Σ E im dG. so suffices to check whether all elements in the fiber Fo(E) are identical.
AY1, A2 E TR. S2,S2 E PD(B):
(A1, (A2, E (A1 As A2 = 12))
(14)
The checks da (A,, 22) Σ are implemented using Ω2 (I- - AA)) which is equivalent due to I - A; being invertible for any A; E RR.. This proves the following:
Theorem 6. Numerical identifiability is in (the promise version of) YR.
Remark 7. Strictly speaking, numerical identifiability is not contained in VIR since it is a promise problem, that is, the outcome is not specified for Σ that are not feasible. VE consists by definition only of classical decision problems, where the outcome is specified for all inputs. So the corre- sponding complexity class is Promisc-VR. Section B contains some more information promise problems for the reader's 's convenience.
ssee Remark for the details. 'Note that membership in PD(n) can be even decided faster. However, this will not change the complexity of overall algorithm.
8

---

However, we can express feasibility in EI::
Lemma 8. Membership in im &G can be expressed in ]R
Proof. We use the expression 3A E RRD. E PD(B) (T- A) A) 92, where we use
Lemma to express S2 PD B) in RR that is, we quantify over an arbitrary matrix Q first and add the ETR expression from Lemma to ensure that Q is in PD(B).
Hence, check in FR whether the input E is feasible and then in VR whether the fiber has only one element. Using Renegar's algorithm, we get:
Corollary 2. Numerical identifiability can be decided in polynomial space.
Generic Identifiability is in PSPACE
Let DIM denote the following problem: Given an encoding of semi-algebraic S and a number d, decide whether dim S 2 d.
Lemma (Koiran 27 The problem DIM is cR-complete. Moreover this is even true when the set is given by an existentially quantified formula in (2)
We use the same notation as in Section 2.1
Let G = (V, be mixed graph. Let Se = (A, (A, 2)] > 1,A IR , E PD(
Observation 10. G is generically identifiable iff dim RD dim PD(B) dim SG.
Proof. As SG CRA x PD( and dim(R" x PD(B)) = dim R² dim PD(B), the hight-hand side just the definition of being generically identifiable.
We postpone the proof that membership in Sa can be expressed in 3R, in favor of first giving our algorithm to decide generic identifiability, using this observation:
Theorem 11. Generic identifiability both in VER and EVR.
Proof. Let G be the given mixed graph. Formulate membership in R., PD(B), and SG instances of ETR using Lemmas 5 and 12 Note that the number of variables and the sizes of these instances polynomial in the size of G. Now we can check whether G is generically identifiable by checking
the condition in Observation 10
We first assume that have oracle access to ETR, that is, we query ETR polynomial number of times. We decide whether generically identifiable as follows:
1. Use Koiran's 's algorithm (see Lemma repeatedly to compute dim Sg by checking whether dim SG 2 for O..... 2n (We could even use binary search.)
2. Compute dim ! and dim PD(B) in the same way Here it suffices to check up to the maximum possible dimension of d = n
3. Accept if dim RD + dim PD(B) > dim Sc. and reject otherwise.
The algorithm is correct by Observation 10 The algorithm above would already show the PSPACE upper bound for generic identifiability.
However, implement the algorithm above by single formula by replacing the repeated use of Koiran's 's algorithm by a big disjunction:
(dim RD 2 di dim PD(B) 2 d2 A dim So < di + dz).
d
see Appendix for why this statement follows from 'While we could compute these dimensions more directly. this is not necessary to obtain PSPACE algo- rithm. However for implementing this algorithm in practice, would advise computing them efficiently.

---

Note that the check dim Sg < d1 d2 needs to be implemented -dim SG 2 d1)) thus being in vR by De Morgan's 's laws. The existential and universal quantifiers are however independent, giving upper bounds of both AनI. and 7VR.
Using Renegar's algorithm this implies: Corollary 3. Generic identifiability can be decided in PSPACE.
only remains to show how to express membership Sg as ETR-formula.
Lemma 12. Membership in Sa can be expressed in ER.
Proof. The membership of some (A, in So can be expressed as A E RD AQ PD(B) A 3E E R
RxX A NERD : (T-A)TTT- -)) =) A - -)) -A) A')=99 Ω A A +
Remark 13. The algorithm of Theorem 17 as is only tests generic identifiability Since the problem
has high degree, one cannol expect that the solutions have easy expressions. However, Renegar's algorithm shows that the solutions are the linear factors of certain polynomial, (33)
7 A Note on Cyclic Graphs
Our results so far have depended on the fact that every matrix I A with IR is invertible if the graph is acyclic. However, if the graph is cyclic, - A is not necessarily invertible. So in this case, we need to explicitly consider the subset Rygg matrices
RR' such that A is invertible.
For matrices Ag E RR and Q4 E PD(B), 21 define fibers as
Fo Qo) = ((A,2) (c(A = @a(A0. Ro), E reg: E PB))
They determine generic identifiability for cyclic graphs in terms of these fibers. That is mixed (cyclic) graph G said to be generically identifiable if [Fa (4)1
for Zariski almost all
Ag E Fog
D and Og E PD(B).
This is the same criterion used for acyclic graphs, except RD. has been replaced by BD twice. Matrix invertibility can easily expressed in ERR using definition of invertibility:
invertible
+ 3B Rnx" xn AB= 1.
Hence, all our upper bounds also hold for general graphs.
Conclusions
Due to double exponential runtime, the state-of the--rrtrrtttt algorithm for the generic identification prob- lem is often too slow to solve instances of reasonable size. For example, Carcia-Puente et al. [22] report that the runtime varies between seconds and 75 days for graphs with four nodes. An in- teresting topic for future work would be to implement the (theoretical) algorithm presented in our paper.
We have given new upper on the complexity generic identifiability, namely PSPACE. More precisely, we showed that it is in MVE and V3R. This can be even improved to VR. It is not necessary to express the dimension of IRD and PD(B) in terms of the theory the reals, but they can be calculated directly, dim RD [D] as well as dim PD(B) proof's for the new notion of numerical identifiability, we conjecture that generic identifiability is hard for VIR, too.
[B]. In the light of our hardness
Acknowledgments and Disclosure of Funding
This research was supported by the Deutsche Forschungsgemeinnccatt (DFG) grant 471183316 (ZA 1244/1-1).
10

---

References
[1] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ERR- complete. In Proc. ACM SIGACT Symposium Theory of Computing (STOC), pages 65-73, 2018.
[2] T.W. Anderson and Herman Rubin. Statistical inference in factor analysis. In Proc. of the Berkeley Symposium on Mathematical Statisties and Probability, page 111. University of Cal- ifornia Press, 1956.
[3] 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 Machin- ery, New York, NY, USA, 2022.
[4] Saugata Basu, Richard Pollack, and Marie- Kraie-FFançoise Roy. Algorithms in Real Algebraic Ge- ometry. Springer, 2003.
[5] Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Training fully connected neural networks is cIR-complete. In Proc. Conference on Neural Information Processing Systems (NeurIPS), 2023.
[6] Bochnak, Coste, and M.F. Roy. Real Algebraic Geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge/ / A Series of Modern Surveys in Mathematics. Springer Berlin Heidelberg, 2013.
[7] Kenneth A. Bollen. Structural equations with latent variables. John Wiley & Sons, 1989.
[8] R.J. Bowden and D.A. Turkington. Instrumental variables. Cambridge University Press, 1984.
[9] Carlos Brito. Instrumental sets. In Rina Dechter, Hector Geffner, and Joseph Y Halpern, editors, Heuristics, Probability and Causality. A Tribute to Judea Pearl, chapter 17, pages 295-308. College Publications, 2010.
[10] Carlos Brito and Judea Pearl. Generalized instrumental variables. In Proc. Conference on Uncertainty in Artificial Intelligence (UAI), pages 85-93, 2002.
[11] Carlos Brito and Judea Pearl. A graphical criterion for the identification of causal effects in linear models. In Proc. AAAI Conference on Artificial Intelligence (AAAI), pages 533-538, 2002.
[12] Michael W. Browne. Generalized least squares estimators in the analysis of covariance struc- tures. South African Statistical Journal, 8(1):1-24, 1974.
[13] Bryant Chen. Identification and overidentification of linear structural equation models. In Proc. International Conference on Neural Information Processing Systems (NeurIPS), pages 1587-1595, 2016.
[14] Bryant Chen, Daniel Kumor, and Elias Bareinboim. Identification and model testing in linear structural equation models using auxiliary variables. In Proc. International Conference on Machine Learning (ICML), pages 757-766. PMIR, 2017.
[15] Bryant Chen, Judea Pearl, and Elias Bareinboim. Incorporating knowledge into structural equation models using auxiliary variables. Proc. International Joint Conference on Artificial Intelligence (IJCAI), pages 3577-3583, 2015.
[16] Mathias Drton. Algebraic problems in structural equation modeling. The 50th anniversary of Gröbner bases, pages 35-86. Mathematical Society of Japan, 2018.
[17] Mathias Drton, Rina Foygel, and Seth Sullivant. Global identifiability of linear structural equation models. The Annals of Statistics, 39(2)885-8886 2011.
[18] Otis Dudley Duncan. Introduction to structural equation models. Academic Press, 1975.
[19] Franklin M. Fisher. The identification problem in econometrics. McGraw- Hill,, 1966.

---

[20] Ronald Aylmer Fisher. Design of experiments. British Medical Journal, 1(3923):554, 1936.
[21] Rina Foygel, Jan Draisma, and Mathias Drton. Half-trek criterion for generic identifiability of linear structural equation models. The Annals of Statistics, 40(3):1682-1713, 2012.
[22] Luis D. García-Puente, Sarah Spielvogel, and Seth Sullivant. Identifying causal effects with computer algebra. In Proc. Conference on Uncertainty in Artificial Intelligence (UAI), pages 193-200 AUAI Press, 2010.
[23] S Gerggorin. Über die Abgrenzung der Eigenwerte einer Matrix. Bulletin de I l'Académie des Sciences de I'URSS. Classe des sciences mathématiques et na, 6:749-7544 1931.
[24] Aaryan Gupta and Markus Bläser. Identification for tree-shaped structural causal models in polynomial time. In Proc. AAAI Conference on Artificial Intelligence (AAAI), pages 20404- 20411, 2024.
[25] Li-tze Hu, Peter M Bentler, and Yutaka Kano. Can test statistics in covariance structure analysis be trusted? Psychological bulletin, 112(2))351, 1992.
[26] Karl G. Jöreskog. A general approach to confirmatory maximum likelihood factor analysis. Psychometrika, 34(2):183-201 202 1969.
[27] Pascal Koiran, The real dimension problem NPy-complete. J. Complex, 15(2)227-2338, 1999.
[28] Daniel Kumor, Bryant Chen, and Elias Bareinboim. Efficient identification in línear structural causal models with instrumental cutsets. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 12477-12486 2019.
[29] Daniel Kumor, Carlos Cinelli, and Elias Bareinboim. Efficient identification in linear structural causal models with auxiliary cutsets. In Proc. International Conference on Machine Learning (ICML), pages 5501-5510. PMLR, 2020.
[30] Bengt Muthen. Latent variable structural equation modeling with categorical data. Journal of Econometrics, 22(1-)):43-65, 1983.
[31] Judea Pearl. Parameter identification: A new perspective. Technical Report R-276, UCLA, 2001.
[32] Judea Pearl. Causality. Cambridge University Press, 2009.
[33] James Renegar. On the computational complexity and geometry of the first-order theory the reals. parts i-iii. Journal of symbolic computation, 13(3):255-352, 1992.
[34] Mareus Schaefer, Jean Cardinal, and Tillmann Miltzow. The existential theory of the reals as a complexity class: A compendium. CoRR, abs/2407..1806. 2024.
[35] Marcus Schaefer and Daniel Stefankovic. Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst., 60(2):172-193, 2017.
[36] Marcus Schaefer and Daniel Stefankovic. Beyond the existential theory of the reals. Theory Comput. Syst., 68(2):195-20) 2024.
[37] Benito van der Zander and Maciej Liskiewicz. On searching for generalized instrumental variables. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1214- 2016.
[38] Benito van der Zander, Johannes Textor, and Maciej Liskiewicz. Efficiently finding condi- tional instruments for causal inference. In Proc. International Joint Conference Artificial Intelligence (IJCAI), pages 3243-3249, 2015.
[39] Benito van der Zander, Marcel Wienöbst, Markus Bläser, and Maciej Liskiewicz. Identification in tree-shaeed linear structural causal models. Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 6770-6792. PMLR, 2022.
12

---

[40] Luca Weihs, Bill Robinson, Emilie Dufresne, Jennifer Kenkel, Kaie Kubjas, Reginald L. McGee II, Nhan Nguyen, Elina Robeva, and Mathias Drton. Determinantal generalizations of instrumental variables. Journal of Causal Inference, 6(1), 2018.
[41] Philip G. Wright. Tariff on animal and vegetable oils. Macmillan Company, New York, 1928.
[42] Sewall Wright. Correlation and causation. Journal of agriculural research, 20(7):557, 1921.
13

---

Appendix
A Edge Identifiability
For edge identifiability, obtain the same results for identifiability itself.
A.1 Hardness of Numerical Edge Identifiability
If we analyze the reduction in Theorem in bit more detail, we can use the same reduction to show Corollary 4. Numerical edge identifiability is vRR-hard.
Proof. If instead starting with an arbitrary QUAD++-nnstanc we start with QUAD++..
instance generated by Lemma [ and Corollary | These instances have distinguished variable y. such that there is always single solution with y = 1 and possibly multiple solutions with y = O. W.l.o.g, let be this distinguished variable. Following the reduction in Theorem 2 we construct graph G and a Σ E im dag such that the fiber Fo(E) isomorphic to the solutions our QUAD++- instance. In particular the value of Åt in the elements of FG(E) is exactly the value of xı in the solutions to the AUAD*+innttame solution, otherwise FFl (Σ)] 22
Thus (E) 1 iff the QUAD++ instance has exactly one
A.2 Upper Bound for Numerical Edge Identifiability
Similarly
14), express numerical edge identifiability the VIR-formula
V Q1 Q2 E PD(B): Φc Q2) (A2, = (A1)s, (Az)es-
(15)
This yields
Theorem 14. Numerical edge identifiability is in (the promise version of) VIR.
Again using Renegar's algorithm we also get
Corollary 5. Numerical edge identifiability can be decided in polynomial space.
A.3 Generic Edge Identifiability is in PSPACE
We modify the algorithm of Section to work with generic edge identifiability for some A.,j rather than generic identifiability. Let St {A, Ω2) [il (A, > 1.A E RD, E PD(B)). Then we have the following analog to Observation I0:
Observation 15. Xij is genericully edge identifiable iff dim RD + dim PD(B) dim St Lemma 16. Membership sig can be expressed in ER..
Proof. We use similar formula Lemma 12
A A ADE Xm M NERP,O @DD(B) (T- A) A) =Q A - (I- AAis # No.)
Theorem 17. Generic edge identifiability both in VER and EVR.
Proof. We use the algorithm of Theorem 11 but replace the So by Si...
Corollary 6. Generic edge identifiability can be decided in PSPACE.
14

---

B Promise problems
We give some background information promise problems for the readers convenience. In classical decision problem I, we are given an input and we have to decide whether I E L (the so-called yes-instances) or x & L (the no-instances). For instance, in the classical SAT problem, we are given a Boolean formula F' in CNF. The yes-instances are the satisfiable formulas and the no-instances are the unsatisfiable one.
Promise problems have a third type of instances, the so-called do-mot-cure-instances On these in- stances, an algorithm can do what it wants and give any output. For instance, consider the problem SAT++ where we ask the question of whether a satisfiable formula in CNF has another satisfying assignment. The yes-instances are all F with exactly one satisfying assignment, and the do-not-care-instanee are all unsatisfiable F. An algorithm solving SAT+ has output "yes" every F with at least two satisfying assign- ments and "no" on every F' with exactly one satisfying assignment. On unsatisfiable formulas, it can output whatever wants. Note that every classical decision problem is also a promise problem with the ho-not-careeinnttaees being the empty set.
all F with at least two satisfying assignments, the no-instances
We can also define many-one reductions for promise problems: A function f 10,0 1) - {0, 1}* is called a many-one reduction from a promise problem L to another promise problem L', if f maps yes- res-instances of L to yes-instances of L' and no-instances of L to no-instances of L'. f can map co-ntt-carr-inntances of L. to any instance of T'. By using similar trick of encoding an additional show that SAT++ is NP-hard, since
satisfying assignment like in the case of ETR we can reduce SAT to it. This reduction maps the unsatisfiable formulas (no-instances of SAT) formulas with one satisfying assignment (no-instances of SAT++) and satisfiable formulas (yes- instances of SAT) to formulas with two or more satisfying assignments (yes-instances of +A Since SAT is a classical decision problem, there are no do-nof-care-instances. SAT++ is, however, not contained in NP for formal reasons, because NP only contains classical decision problems.
C Semialgebraic sets
For the reader's convenience, give brief introduction semialgebraic sets and discuss the notations important for this work. For details and proofs, we refer to the book [4].
A semialgebraic set in R2" is a finite Boolean combination (finite number of unions and intersections) of sets of the form [(ar..... ).n)) [(Z1....,,,) > 0} and {(x1).... xn) g( 2 0}. Here and are real polynomials in variables.
A semialgebraic function is a function IR" + R with semialgebraic graph, that is, the set of all {(x, ((x)(()) x E ]"] is a semialgebraic set.
From this definition of semialgebraic sets, it is easy to see that semialgebraic sets are the solutions of ETR-instances, that is, all (.1,-.-, 2ra) satisfying yaar,....,, in 2 form semialgebraic set. From Tarski's theorem (see (4), it follows that semialgebraic sets allow quantifier elimination, that is, all (I1, Tn, satisfying
Ft ... (ar --., y/ -1.-....2 Ve)
form semialgebraic set, where 2b (like yp is quantifier-free Boolean formula the basis AV,A,- and a signature consisting of the constants and 1, the functional symbols + and and the relational symbols <, S, and (Ii,..., Fn, ......................... yt)) satisfying y form a semialgebraic set. Tarski's 's theorem tells us that we still get a semialgebraic set when are projecting the .h.....31 Vt away using the existential quantifiers. This is used frequently in our proofs.
depends two sets of variables. It is clear that all
Definition 4. A semialgebraic set S has dimension d if there exists a d-dimensional coordinate subspace such that the image of under the canonical projection onto this subspace has a nonempty interior and there is no such subspace of dimension + 1.
Above, by d-dimensional coordinate subspace, we mean the subspace of R. of all points x such that z; = 0 for i & 1 for some subset I S .I) and |Z| = d.
Theorem 18 (see e.g. (6). Let be a semialgebraic set. Then dimension as a semialgebruic set (as in Definition 4 equals the dimension of its Zariski closure as an algebraic set.
15

---

D Koiran's algorithm
Koiran mainly works in the so-called BSS-model of real computation. In this model, one is also allowed to use arbitrary real constants in the algorithm as well as real inputs. In ER, we only allow the constants and 1 and the inputs are given by some binary encoding. However, Koiran also considers the bit model. [27 Theorem 6] proves the computational equivalence of DIM and 4FEAS the model. Since 4FEAS compomeeeeee that at the time Koiran wrote his paper, the class ] was not formally defined and therefore, Koiran does not mention explicitly.
[35], this implies that DIM is Co-coplete.. Note
For the moreover part, note that [27 Section 1.1] discusses the representations of semi semi-algebraic sets that are supported by his proof. There he mentions existentially quantified formulas explicitly.
16

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The two main claims from the abstract can be found as Corollary 3 and The- orem In the introduction, we mention five items in the subsection "Our contributions". They correspond to Corollary Theorem [1] Theorem Corollary 2 and the results in Appendix A All results are formally proved.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: Our main algorithm (provably) complete and thus does not have limitations regarding the correctness of the output. This is an algorithms theory paper, we consider classical worst case complexity. Therefore, there are no limitations regarding the inputs. The complexity upper bounds are formally proved.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex, system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
17

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper contains all proofs in the main part, with the exception of the proofs about edge identifiability, which are almost exactly the same the proofs from the main part with slight modifications. They can be found Appendix A instead. All proofs are formal and the assumptions are clearly stated. All theorems, formulas, and proofs in the paper are numbered and cross-referenced. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple-
mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not contain experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If contribution a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
18

---

(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not contain any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.com
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
ctrips.cc/public// galliccguudde gwtgg/uideeeeee/ Ctteee//ooSSuubiseeee ssisnnolicyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
19

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory. time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:pp:s///arrpps..ppppppliiiie
Answer: [Yes]
Justification: This is a purely theory based paper with no experiments. No data sets were used. No crowdsoureing contract work was done.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdictio).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is purely theory based paper. We do not expect an improvement in the complexity of identification algorithms to have any negative societal impact.
20

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is theory paper with no data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
21

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, patasets.paperswittte [paperswithcode www.comm/aaa.oc condattsett has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not contain any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not contain any experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not contain any experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
22

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "pVBaBLuJX9", "reviewer": "Reviewer_ToDP", "summary": "The paper tries to attach an important theoretic problem: the complexity of identification in linear SEMs. The author proposed an algorithm for generic identification with exponential running time while previous the best algorithm is in double exponential running time.", "questions": "See weakness.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well organized and presented. For a reader who is not very familiar with the complexity theory, the writer make the conception such as $\\forall \\mathbb{R}$ easy to understand. \n\n2. The over all idea to connect the identification with ETR and QUAD is good and easy to follow.", "weaknesses": "Purely from complexity the current algorithm is better than state-of-the-art, however we do not have any knowledge about the constant computational overhead in the algorithm. When applying the theory in the paper to build a practical algorithm, this might also be important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We agree it is not guaranteed that theoretically faster algorithms will be better in practice. We are working on an implementation of our algorithms. However, experience shows that drastic improvements on the theoretical running time typically come with similar improvements on the practical side. (But we admit that there are sometimes exceptions.)\n\nWe would like to emphasize that since the formulation of the parameter identification problem in linear SEMs in the 1960s, this problem has been widely studied by econometricians and sociologists, and more recently by the ML, AI,  and statistics communities, but no (complete) algorithm has been found that matches the general applicability of the Gröbner basis approach and that runs faster than in doubly-exponential-time. For the first time, our work provides a new algorithm that states a constructive upper bound on the computational complexity of the generic identification problem which significantly improves the doubly-exponential bound of Gröbner bases.\n\nWe decided to publish our results in its current theoretical form because (1) it shows (for the first time) that it is possible to avoid the method based on Gröbner bases and (2) it proposes a new approach (using semi-algebraic sets and Koiran's algorithm) to solve the identification problem, which would be of interest to the NeurIPS community. We believe that our results also provide an important first step towards achieving an implementable algorithm that can handle cases with sizes much larger than those possible using state-of-the-art methods (see, e.g., Garcia-Puente et al. [22]). \n\nFor the related problem of numerical identifiability, we get an almost tight complexity classification. A $\\forall \\mathbb{R}$ lower bound, which is to our knowledge the first lower bound for any such identification problem, and a(n almost) matching upper bound, namely promise $\\forall \\mathbb{R}$ or $\\forall \\exists \\mathbb{R}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9L9glqQ3Hr", "reviewer": "Reviewer_WjE6", "summary": "This paper is a theoretical examination of the problem of parameter identifiability in structural equation models for mixed graphs (which has applications in causal modeling), significantly improving upon known upper bounds and establishing a hardness result for the problem's complexity.", "questions": "My main questions are about the \"causal\" aspect of the work as well as implications for other model classes.\n\n1. Don't all these results hold for Gaussian recursive mixed graph models generally instead of specifically causal ones? In other words, I don't see how any of the results make use of causal assumptions (like Reichenbach's common cause assumption or the causal Markov assumption) or interventional settings. To be clear, I don't think this is a bad thing—I just want to make sure I'm not missing some assumptions that limit the results.\n2. Do these results apply immediately to Gaussian DAG models? Or only the upper bound? Or is there some fundamental difference in the DAG setup?\n\nNow some technical questions:\n\n3. In the equation on lines 33 and 129, shouldn't it be $\\epsilon_j$ to match the $X_j$ on the left-hand side?\n4. In lines 43,44 and again 154, 154, it's claimed that knowing the $\\lambda$s is sufficient for recovering the $\\omega$s, but one also needs to know/estimate $\\Sigma$, right? While this is reasonably clear to an expert, it's not explicitly mentioned in those sentences.\n5. In line 214, doesn't it rather reduce to $x_1 = \\ldots = x_n = 0$?\n6. Can the authors elaborate on the last sentence of the proof of Theorem 2, especially after \"and\" (lines 269, 270)? It could help to rephrase Corollary 1 in those terms or add an explicit Corollary 1'.\n7. What is meant with \"By standard simulation results,...\" on lines 6, 7? I don't see any simulations results in the paper or supplement.", "limitations": "Limitations (such as restriction to the linear Gaussian setting and only having theoretical results) are clear from a detailed reading, but they could (and should) be more explicitly mentioned as limitations of the work in, e.g., the Intro.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**Originality**: The paper has originality (by using the existential theory of the reals to study complexity of parameter identifiability in probalistic graphical models), and this originality leads to an interesting new perspective and good results on the problem of study.\n\n**Quality**:  The paper is of high technical quality (other than a few presumed typos).\n\n**Clarity**: I find the proofs and technical writing to be rigorous and clear, and the positioning compared to previous complexity results is quite clear.\n\n**Significance**: The paper should have at least moderate impact in the sub-areas Causal Inference and Graphical Models (and high impact in the sub-sub-area Algebraic Statistics). Specifically, this paper established foundational complexity results that have wide relevance in causal modeling. Additionally, the paper leads to natural follow-up work in the form of implementing the presented theoretical algorithm and approaching similar identifiability questions for other model classes from the same perspective.", "weaknesses": "The main weakness (other than those mentioned in the Questions and Limitations sections below) is the clarity of the non-technical writing. There is not much to guide the reader through the technical parts, so I worry non-experts will have too much difficulty to see the value of these theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Answers to main questions:\n\n1. The Gaussian recursive mixed graph models imply causal assumptions. The value (distribution) of each node is only affected by its parents and the bidirected edges. That yields Reichenbach's assumption, that if two nodes are not independent, there is either a direct cause (through their parents) or a common cause (through a bidirected edge). Some variant of the Markov assumption also holds if one considers the bidirected edges as parents.\n\n2. There are different kinds of DAG models, with unobserved variables and without unobserved variables.\n\nThe one without unobserved variables is trivially identifiable. It is equivalent to the Gaussian recursive mixed graph models without bidirected edges.\n\nThe one with unobserved variables is more general than mixed graph models, so one can expect the lower bound to hold. The classic reduction of a mixed graph model to the DAG model is to replace any bidirected edge X <--> Y by a path through an \"unobserved\" node U, i.e. X <-- U --> Y. The covariance of U influences the covariances of X and Y. If the identification problem in the original mixed graph means solving equation system (1), then the reduced identification problem is solving an equation system (1') which is obtained from (1) by replacing each $\\omega_{XY}$ with the product $\\lambda_{XU}\\lambda_{YU}$ where the solution must not contain any $\\sigma$ involving the unobserved variables. Now a solution to (1) is also a solution to (1') after replacing the omegas (because (1) has no variables involving the unobserved variables).  \n\n\nAnswers to technical questions:\n\n3. You are right about lines 33 and 129, the index is wrong. Thanks for pointing this out, we will correct it.\n\n4. That is right, we assume (as do all the previous results that we cite) that $\\Sigma$ is given. We will point this out more clearly in the mentioned lines.\n\n5. That is true, thanks for pointing this out as well. We will correct this.\n\n6. The classes $\\forall \\mathbb{R}$ and $\\exists R$ are co-classes in the sense that when a problem $L \\in \\forall \\mathbb{R}$, then its complement $\\bar L$ is in $\\exists R$ and vice versa. The complement of QUAD$^{++}$ is the following problem: Given a set of quadratic equations with at least one solution, is this solution the only solution. It is a $\\forall \\mathbb{R}$ complete problem. By Lemma 3, our constructed instance is identifiable iff the given satisfiable set of quadratic equations has exactly one solution. So we have a reduction from the complement of QUAD$^{++}$, which is $\\forall \\mathbb{R}$ hard, to Numerical Identifiability and therefore, Numerical Identifiability is also $\\forall \\mathbb{R}$ hard.\n\n7. Standard simulation means that PSPACE is contained in EXPTIME. It is easy to see that an algorithm that is polynomially space bounded is also exponential time bounded (modulo some small technical details). It can be found in standard text books on complexity, like Papadimitriou, Computational Complexity, Pearson, 1993. We will add the reference.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8a5zHXNymD", "reviewer": "Reviewer_Q8jB", "summary": "This paper looks into the parameter identification problem in linear structural causal models using only observational data. Under the Gaussian linear SEMs, the paper provides a polynomial-space algorithm that runs in exponential time. The paper also provides the hardness of the problem.", "questions": "- There should be a constraint on the diagonal of matrices in PD$(m)$.\n- My major question is regarding the construct of $G$ in Section 4:\n  - The left figure in Figure 3 has all $\\lambda$ with subscript $r$. Isn't it $i$ for the left and $j$ for the right?\n  - There seem to be some typos in equation (11) as $\\lambda_{a_{\\ell},i}$ appears in all three summations. Is this equation obtained by expanding equation (10)?\n  - Can the authors explain Observation 4 a bit more? I am not quite sure why this is the case.\n- The paper mentioned the algorithms in multiple parts. Does it mean the algorithm starts from line 320? And does this algorithm learn the final parameters or only give generic identifiability?\n- I'd suggest having a link from Koiran’s algorithm to Appendix D.", "limitations": "The authors state all assumptions.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "In my knowledge, the methods and resutls are new. The paper investigated this traditional problem from computational complexity theory's view, which seems interesting to involved in this problem. The paper linked this parameter identification problems to the NP/coNP and PSPACE and then provide hardness and bounds based on it. Through I could not entirely follow the steps in the proof, but the paper seems theoritically sound.", "weaknesses": "- The algorithm has some assumptions about the model itself. For instance, the model assumes normal noises and (known) topological sorting. But this does not weaken the paper's contribution. \n- The algorithm needs access to an oracle. \n- The notations can be further explained to enhance the reading flow; maybe give a few sentence definitions when the notions first appear in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding weaknesses:\n\n- We agree that learning the graph structure of the causal model and/or the topological ordering of variables is a difficult and very challenging task. However, we would like to emphasize that learning causal structures and/or the topological orderings was not the subject of this work and, as it is commonly accepted in studies on the parameter identification in linear SEMs, we assume that such a structure is given as an instance of the problem. It is also common to assume that noises are normal.\n We would like to point out that while these assumptions make the upper bounds easier in some sense, they make hardness results more difficult to prove. So they only work partly in our favor.\n\n- We would like to explain that our algorithm (in the proof of Theorem 11) does not need to have access to an oracle. To make the description of the algorithm modular and easy to understand, we first provide an algorithm having oracle access to ETR and next we explain that using Renegar’s algorithm the ETR queries can be computed in PSPACE (Corollary 3). Therefore, we only use them to make the statements more convenient. You can think of it as procedures that we call. The oracle calls can always replaced by actual algorithms. We will point this out more clearly.\n\n- We thank the reviewer for commenting on the need to add some supporting explanations to the designations.\n\n\nRegarding Questions:\n\n- Being positive definite has some implications on the diagonal, but depending on the definition, it is not always stated explicitly. For instance, in the first definition used in the proof of Lemma 5, there is some explicit restriction stated, while the second definition in the proof does not have such an explicit restriction. Since both definitions are equivalent, there is an implicit restriction in the second definition. Being diagonally dominant implies positive definiteness but the other direction is not true in general.\n\n- We apologize for the confusion and thank you for pointing this out. A few indices are not correct, see below for corrections. (We made some last minute changes and should not have done this.)\n\n  -- On the left-hand side in Figure 3, the r's should be i and j, respectively.\n\n  -- In the sum in the middle of (11), $\\lambda_{a_\\ell,i}$ should be $\\lambda_{b_k,j}$. We are sorry for the typo. The equation is obtained from (10) by simply writing down the entries of the matrix product and looking at entry (i,j).\n\n  -- Obseration 4 follows from (10) and the fact the our graph has only two layers. Since i and j are both in the top layer, $\\sigma_{i,j}$ can only appear in the equation in (10) that corresponds to entry (i,j) in the matrix. It can never appear multiplied with any $\\lambda_{k,\\ell}$, because then a least one of i or j needs to be in the bottom layer. The value $\\sigma_{a_\\ell,j}$ can only appear in an equation corresponding to a  missing edge $\\{h,j\\}$ that contains j and when there is a directed edge $(a_\\ell,h)$. But there is only one leaving $a_\\ell$ by construction and this edge ends in i, hence $h = i$. The same is true for $\\sigma_{b_k,i}$. For $\\sigma_{a_\\ell,b_k}$ to appear in an equation given by a missing edge $\\{g,h\\}$, there have to be directed edges $(a_\\ell,g)$ and $(b_k,h)$. Again by construction, $g = i$ and $h = j$.\n\n- The algorithm itself starts in line 320. But it calls subroutines that are described earlier. In step 1, we obviously call Koiran's algorithm. In step 2, we call the algorithm from Lemma 5 to decide membership in PD(B). In step 3, we use the algorithm from Lemma 12 as well as Koiran's algorithm to compute $\\dim\\ S_G$. We will state this more explicitly.\n\n- The algorithm decides whether the instance is generically identifiable. If it is, it will automatically also obtain the parameters, since the ETR solver computes them on the way.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8KDQ2LNaGA", "reviewer": "Reviewer_gLJ2", "summary": "The submission studies the problems of generic parameter identification and numerical identification, both of which represent prominent tasks in causal analysis. The results include a PSPACE (i.e., single-exponential) algorithm for generic parameter identification, as well as ForallR-hardness and a single-exponential time algorithm for numerical identification. The submission also extends these results to the closely related setting of edge identifiability.", "questions": "No additional questions, but the authors are welcome to respond to the specific concerns raised above.", "limitations": "The limitations are adequately discussed.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The studied problems are computationally challenging and seem to be relevant for the NeurIPS community.", "weaknesses": "-The restriction to recursive models comes abruptly and is not motivated or discussed in the submission at all. A number of questions are left completely unanswered, such as: Are recursive models common? Have they been studied before? Do they occur in practice? Do the results generalize beyond recursive models? Is there a specific reason one should restrict one's attention to these models?\n\n-The definition of the problems studied do not seem written in sufficiently accessible language and assume that readers are already familiar with several specialized concepts. As one example, \"Zariski almost all\" and \"Zariski closure\" is never defined. The submission would also be much more accessible if it included at least some high-level examples of problem instances and solutions.\n\n-In terms of writing, several of the results are established using only semi-formal language and without what I would consider sufficient rigor. For instance, the construction for the proof of Theorem 2 is described using inline examples and descriptions, but given the crucial importance of the construction for the proof I would have expected the core properties of the construction to be established and formalized via lemmas or claims.\n\n-The results seem to be obtained primarily by cleverly combining known techniques and results, with little new insights required. In particular, the main results in Sections 5 and 6 essentially follow via direct encodings into appropriate fragments of the Theory of the Reals.\n\nMinor comments:\n-row 48: \"using alone Sigma\" should be \"using Sigma alone\"\n-row 71: malformed sentence\n-row 301: \"So we can check in...\" should be \"Hence, we can check in...\"\n-row 340: \"*the* generic identification problem\". Also, missing full stop at the end of the footnote.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Recursive (or, in graphical language, acyclic) models are fairly standard and most commonly used in causality. They are the basic structural causal models used in causal inference (e.g. in the famous Pearl's do-calculus, Markov-equivalence of causal models, etc.) and in causal structure learning (e.g., the well-known PC algorithm by Spirtes and Glymour or GES algorithm by Chickering learn from observed data acyclic models). Also (causal) Bayesian models are represented by such acyclic graphs. Furthermore, when restricting general causal models to linear ones (which are the subject of our work), recursive models are most commonly used. In particular the papers studying parameter identification in linear SEMs cited in our work [8, 10, 11, 14, 15, 24, 28, 29, 31, 36, 37, 38, 40, 41] assume recursive causal models. Since some recent works try to consider cyclic models as well, we have indicated in line 35 that our work assumes the standard model. Nevertheless, as we observed very recently, this restriction is not needed and our results can be generalized to non-recursive models. We will add an explanation in the final version.\n  \n- Identification in linear structural causal models naturally reduces via Equation (10) in the paper to solving polynomial systems of equations over the reals. Therefore, tools from commutative algebra and real algebraic geometry are inherently needed. We agree that we should have given short inline descriptions of the terms you mention. We will do so and also add a more detailed appendix on the basic algebraic concepts used.\n\n- We hoped that it would be easier and more accessible if we develop our constructions in a textual manner. We find this quite hard to balance, since the audience of the paper is quite diverse. Other reviewers wanted more informal explanations and less proofs.  Note that the proof of Theorem 2 for instance is still a rigorous proof, it is a so-called \"gadget-based\" proof, which are used commonly. The two SCMs in Figure 4 are not just examples. They are our basic building blocks. They can be instantiated in such a way that they implement the equations given in (4), the basic building blocks of a QUAD^{++} instance. The gadget on the right-hand side implements the equation ab - c = 0, and the other gadget all other four equations with different instantiations of the $\\sigma$-values. This is described right after Figure 4. Then one simply takes these basic building blocks and combines them as described in the proof of Theorem 2 to encode the whole QUAD^{++} instance. We will expand the explanation of the proof structure accordingly.\n\n- Large parts of our work are conceptual. The complexity of generic identification has been an open problem since the 1960s. In hindsight, the proof looks easy, but no one made this connection to the existential theory of the reals as well as the result by Koiran before. Moreover, no hardness results for identification were known before.\n\n- Thank you for pointing out the grammatical errors/typos, we will correct them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pq6VaHhn9r", "reviewer": "Reviewer_Gx9Z", "summary": "The paper examines the computational complexity of Generic and Numerical Identifiability problems. It provides some reduction from these problems to R complete classes. Based on these results, the paper proposes an algorithm for Generic Identifiability, which improves the state-of-the-art double exponential time.", "questions": "1- Is it possible to conduct an experiment to compare your algorithm with previous algorithms?\n\n2- Could you elaborate on the importance of the results and the novelty of proofs? The reductions seem very natural.\n\nI recommend to revise Sections 4, 5, and 6 as the results are very compact and ambiguous. I could not follow very well.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1- The paper proposed new findings on complexity of different various causal identifiability problems.\n\n2- The results demonstrate that these problems can be decided in PSPACE.\n\n3- The papers provided a comprehensive literature review in introduction.", "weaknesses": "1- The importance of results and their technical novelty are not clearly discussed.\n\n2- The main part primarily comprises theorems proofs, which are not completely clear. It would be beneficial to move some parts to the appendix and include more intuition and discussion in the main part.\n\n3- The paper lacks experimental results demonstrating the correctness of the proposed algorithm and the improvement in running time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Answer to questions: \n\n1. At the moment, we consider the main contribution of the paper on the theoretical side. We are currently working on implementations.\n\n\n2. We would like to emphasize that since the formulation of the parameter identification problem in linear SEMs in the 1960s, this problem has been intensively studied by econometricians and sociologists, and more recently by the ML, AI and statistics communities. The key importance of parameter identification (from observed data) is that the inferred parameters can be used to estimate causal effects, especially in cases where randomized controlled trials are not possible.\n\nHowever, despite decades of extensive research, no (complete) algorithm has been found that matches the general applicability of the Gröbner basis approach and thus runs faster than in doubly-exponential-time. Moreover, no non-trivial lower bound (hardness result) on the computational complexity of this problem has been established which would justify the high computational complexity of state-of-the-art algorithms. In our work, we give a novel algorithm that provides a constructive upper bound on the computational complexity of the generic identification problem, which significantly improves on the best-known doubly-exponential bound. Moreover, we give the first hardness results for numerical parameter identification in linear SEMs showing that it is hard for the complexity class ∀R.\n\nThe proof technique provided in our paper is novel. In hindsight, the proofs in Sections 5 and 6 look easy, but no one made this connection to the existential theory of the reals as well as the result by Koiran before. To the best of our knowledge, this proof technique has not been used before for linear causal model analysis, which would be of interest to the NeurIPS community.\nFurthermore, the reduction in Section 4 is quite astonishing, since already SCMs with only two layers turn out to be hard.\n \nRegarding your recommendation to revise Sections 4, 5, and 6:\n\nWe think that our proofs are quite clear. However, when writing for diverse communities, it is always challenging to balance between intuition and mathematical rigor. We thank you for your advice and will follow it by moving more technical parts to the appendix and adding more intuition.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
- We thank the reviewers for their helpful comments. We make some remarks here addressing questions that were raised by more than one reviewer. Specific questions of the referees are discussed in the individual answers.

- We would like to stress that the identification in structural causal models is an old problem (at least for ML/AI standards) with a long history. Despite all the efforts, only very little is known about the computational complexity of identification. We are not aware that any general hardness results. Furthermore, the currently best running time of a complete algorithm for generic identification is doubly exponential. It is based on Gröbner bases and is almost 15 years old. We here obtain the first theoretical improvement since then by giving an algorithm in PSPACE, which implies an exponential improvement in running time. Moreover, we complement this with an almost matching lower bound for a related identification problem (Numerical identification).

Meta-review: This paper addresses the complexity of parameter identification in linear Structural Equation Models (SEMs), introducing a new algorithm that significantly improves upon the previously known double-exponential time algorithms. The paper’s contributions include both theoretical advancements, such as establishing an upper bound on computational complexity, and the first hardness results for numerical identification in linear SEMs. While reviewers acknowledged the importance of these results, they also noted areas for improvement, including the need for clearer explanations and more intuitive presentations. Given the strong technical contributions are strong, the paper is recommended for acceptance. The authors are suggested to improve the clarity of writing.
Decision: Accept (poster)