Constrained Nonnegative Gram Feasibility is $\exists\mathbb{R}$-Complete
We study the computational complexity of constrained nonnegative Gram feasibility. Given a partially specified symmetric matrix together with affine relations among selected entries, the problem asks whether there exists a nonnegative matrix $H \in \mathbb{R}_+^{n\times r}$ such that $W = HH^\top$ satisfies all specified entries and affine constraints. Such factorizations arise naturally in structured low-rank matrix representations and geometric embedding problems. We prove that this feasibility problem is $\exists\mathbb{R}$-complete already for rank $r=2$. The hardness result is obtained…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.19976
curl -X POST /api/v1/records/arxiv/2603.19976/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.19976/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'