2021/03/03 by Tobias Boege, Boege, Tobias
Engineering · Mathematics · #05B20 #14P10 #15A15 #51A25 #62R01 #Advanced Topics in Algebra #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Mathematics and Applications #Statistics Theory (math.ST) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2103.02589
openalex publication_date 2021/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an encoding of a polynomial system into vanishing and non-vanishing constraints on almost-principal minors of a symmetric, principally regular matrix, such that the solvability of the system over some field is equivalent to the satisfiability of the constraints over that field. This implies two complexity results about Gaussian conditional independence structures. First, all real algebraic numbers are necessary to construct inhabitants of non-empty Gaussian statistical models defined by conditional independence and dependence constraints. This gives a negative answer to a question of Petr Šimeček. Second, we prove that the implication problem for Gaussian CI is polynomial-time equivalent to the existential theory of the reals.