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.
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.
**Quality**: The paper is of high technical quality (other than a few presumed typos).
**Clarity**: I find the proofs and technical writing to be rigorous and clear, and the positioning compared to previous complexity results is quite clear.
**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.
Questions
My main questions are about the "causal" aspect of the work as well as implications for other model classes.
1. 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.
2. Do these results apply immediately to Gaussian DAG models? Or only the upper bound? Or is there some fundamental difference in the DAG setup?
Now some technical questions:
3. In the equation on lines 33 and 129, shouldn't it be $\epsilon_j$ to match the $X_j$ on the left-hand side?
4. 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.
5. In line 214, doesn't it rather reduce to $x_1 = \ldots = x_n = 0$?
6. 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'.
7. 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.