Search papers, labs, and topics across Lattice.
This paper investigates the complexity of verification problems associated with Binarized Neural Networks (BNNs), focusing on satisfiability and robustness under uniform image occlusion. The authors establish that BNN satisfiability is NP-complete by reducing it from the Boolean satisfiability problem (SAT), highlighting the inherent computational challenges. In contrast, they introduce a polynomial-time algorithm for checking robustness against uniform occlusion, leveraging the piecewise-constant nature of the network's output under such conditions.
BNN satisfiability is NP-complete, but robustness verification can be achieved in polynomial time through clever structural insights.
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.
