{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-20","reactions":{}}