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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-22 Page: https://delphi.science/r/arxiv/2607.20013 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.…