The Certification Limits of KS-Type Layer Relaxations: A Square-Root Ceiling and Its Breakdown
A separable bilinear layer relaxation assigns a population cost to each layer and a nonpositive bilinear coupling to each pair of layers, then excludes a profile span whenever the relaxed minimum exceeds a reference value. We ask what a Kuznetsov-Sahinidis-type relaxation can certify at best. Let gamma = g(1) be the singleton-layer cost. For every valid relaxation with gamma > -1/2, every reference bounded per particle, and every underlying system satisfying two elementary low-energy witness conditions, we prove that the certified deficit N - rho(N) is at most of order sqrt(N), with an…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.12134
curl -X POST /api/v1/records/arxiv/2607.12134/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.12134/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'