{"id":"arxiv/2607.12134","url":"https://arxiv.org/abs/2607.12134","tags":["math.OC"],"score":0,"title":"The Certification Limits of KS-Type Layer Relaxations: A Square-Root Ceiling and Its Breakdown","domain":"math.OC","source":"arxiv","authors":["Guillaume Lecomte"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}