Parameterized Hardness of Zonotope Containment and Neural Network Verification

ArXi:2509.22849v2 Announce Type: replace-cross Neural networks with ReLU activations are a widely used model in machine learning. It is thus important to have a profound understanding of the properties of the functions computed by such networks. Recently, there has been increasing interest in the (parameterized) computational complexity of determining these properties. In this work, we close several gaps and resolve an open problem posted by Froese [COLT '25] regarding the parameterized complexity of various problems related to network verification.