Further R -complete problems with PSD matrix factorizations

DOI10.1007/S10208-023-09610-1MaRDI QIDQ6592116zbMATH OpenFDO

Authors Ya. N. Shitov

Publication date 24 August 2024

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10208-023-09610-1

zbMATH Keywords

computational complexitycpsd rankpsd rank

Mathematics Subject Classification ID

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

Recommendations

• The complexity of positive semidefinite matrix factorization
• Positive semidefinite rank
• Some upper and lower bounds on PSD-rank
• Rational and real positive semidefinite rank can be different
• Matrices of bounded psd rank are easy to detect

Cites work

• A polynomial-time algorithm for computing low CP-rank decompositions
• Algorithms for positive semidefinite factorization
• Completely positive semidefinite rank
• Compressibility of Positive Semidefinite Factorizations and Quantum Models
• Computing a nonnegative matrix factorization -- provably
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Conic formulations of graph homomorphisms
• Correlation matrices, Clifford algebras, and completely positive semidefinite rank
• Extended formulations for polygons
• Fixed points, Nash equilibria, and the existential theory of the reals
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• Learning the parts of objects by non-negative matrix factorization
• Linear conic formulations for two-party correlations and values of nonlocal games
• Linear vs. semidefinite extended formulations
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Lower bounds on the size of semidefinite programming relaxations
• Matrices of bounded psd rank are easy to detect
• Matrices with high completely positive semidefinite rank
• Maximum semidefinite and linear extension complexity of families of polytopes
• MIP* = RE
• Non-closure of the set of quantum correlations via graphs
• Nonnegative rank depends on the field
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• On ranks of regular polygons
• On the combinatorial and algebraic complexity of quantifier elimination
• On the complexity of nonnegative matrix factorization
• 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
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• On vector configurations that can be realized in the cone of positive matrices
• Polytopes of minimum positive semidefinite rank
• Positive semidefinite rank
• Realizability of graphs and linkages
• Realization spaces of 4-polytopes are universal
• Some provably hard crossing number problems
• Some upper and lower bounds on PSD-rank
• The art gallery problem is \(\exists \mathbb{R}\)-complete
• The complexity of positive semidefinite matrix factorization
• The nonnegative rank of a matrix: hard problems, easy solutions
• The phaseless rank of a matrix
• The set of quantum correlations is not closed
• Universality of Nash Equilibria
• Which nonnegative matrices are slack matrices?
• Worst-case results for positive semidefinite rank

Cited in

(2)

• Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
• Further restricted versions of the nonnegative matrix factorization problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6592116)