{"id":"arxiv/2607.20013","url":"https://arxiv.org/abs/2607.20013","tags":["math.OC"],"score":0,"title":"Order-2 Tightness of Block-Sparse SOS Relaxations for One-Layer ReLU Network Verification with a Matching Input-Sharing Graph","domain":"math.OC","source":"arxiv","authors":["Godai Azuma","Sunyoung Kim","Makoto Yamashita"],"reviews":0,"subject":"math.OC","summary":"Azuma, Kim, and Yamashita formulated the verification problem for one-layer ReLU networks as a quadratically constrained quadratic program and established tight semidefinite relaxations for the edgeless case and for one-unit settings. In this work, we represent the sharing pattern of undecided ReLUs over a box input set through an input-sharing graph and focus on the case where this graph is a matching. We then derive an explicit, checkable sufficient condition for the tightness of the order-$2$ block-sparse SOS relaxation associated with the connected-component decomposition of this graph.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-22","reactions":{}}