Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations

Factorization of matrices (15A23) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vector spaces, linear dependence, rank, lineability (15A03)

Cites Work

Unnamed Item
Conic formulations of graph homomorphisms
A polynomial-time algorithm for computing low CP-rank decompositions
Matrices with high completely positive semidefinite rank
Polytopes of minimum positive semidefinite rank
On vector configurations that can be realized in the cone of positive matrices
Linear conic formulations for two-party correlations and values of nonlocal games
Some upper and lower bounds on PSD-rank
Fixed points, Nash equilibria, and the existential theory of the reals
Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
Extended formulations for polygons
On the existence of 0/1 polytopes with high semidefinite extension complexity
Positive semidefinite rank
Worst-case results for positive semidefinite rank
Some provably hard crossing number problems
On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
Maximum semidefinite and linear extension complexity of families of polytopes
Non-closure of the set of quantum correlations via graphs
Completely positive semidefinite rank
Algorithms for positive semidefinite factorization
Nonnegative rank depends on the field
Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
Hilbert's Nullstellensatz is in the polynomial hierarchy
Which nonnegative matrices are slack matrices?
Realizability of Graphs and Linkages
Lower Bounds on the Size of Semidefinite Programming Relaxations
Compressibility of Positive Semidefinite Factorizations and Quantum Models
Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone
On the Complexity of Nonnegative Matrix Factorization
On the combinatorial and algebraic complexity of quantifier elimination
Matrices of Bounded Psd Rank are Easy to Detect
The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions
On Ranks of Regular Polygons
THE SET OF QUANTUM CORRELATIONS IS NOT CLOSED
Realization spaces of 4-polytopes are universal
Correlation matrices, Clifford algebras, and completely positive semidefinite rank
The Phaseless Rank of a Matrix
The art gallery problem is ∃ ℝ-complete
Learning the parts of objects by non-negative matrix factorization
The Complexity of Positive Semidefinite Matrix Factorization
Linear vs. semidefinite extended formulations
Computing a nonnegative matrix factorization -- provably
Universality of Nash Equilibria
MIP* = RE

This page was built for publication: Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations