Id: arxiv/2603.19976 Url: https://arxiv.org/abs/2603.19976 Tags: math.OC, cs.CC Score: 0 Title: Constrained Nonnegative Gram Feasibility is $\exists\mathbb{R}$-Complete Domain: math.OC Source: arxiv Authors: Angshul Majumdar Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-20 Page: https://delphi.science/r/arxiv/2603.19976 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…