Some Complexity Results for Robustness Verification for Binarized Neural Networks
Harshit Goyal, Sudakshina Dutta
cs.LG cs.CC
Abstract
This paper studies the computational complexity of verification problems for Binarized Neural Networks (BNNs), where activations (and sometimes weights) are binary. We analyze two problems: satisfiability and robustness under uniform image occlusion. We show that BNN satisfiability is NP-complete via a reduction from Boolean satisfiability problem (SAT), and that uniform occlusion induces a piecewise-constant structure in the network output, enabling a polynomial-time robustness-checking algorithm.
Topics
Classified with taxonomy v2 on Wed, 2 Sept 2026.