Information Accessibility Limits in Structured NP Search
We study the problem of locating violating principal minors in matrix families lying near the boundary of P-matrices. Rather than viewing this search problem purely through computational complexity, we analyze it from an information-accessibility perspective. We show that, despite strong underlying algebraic structure, the location of a violating subset may remain difficult to infer through local queries. In the sparse-violation regime, local observations typically provide only weak eliminative power, and polynomially many queries accumulate only vanishing mutual information about the hidden…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.00953
curl -X POST /api/v1/records/arxiv/2605.00953/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.00953/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'