mlsanityData to 14 Oct 2026

Some Complexity Results for Robustness Verification for Binarized Neural Networks

arXiv 2606.18918 ↗First posted 17 Jun 2026cs.LG cs.CCcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper investigates the computational complexity of verification problems for Binarized Neural Networks (BNNs), in which activations and weights are binary. Specifically, we study three verification problems. First, we prove that checking the satisfiability of a linear property for a BNN is NP-complete via a reduction from the Boolean Satisfiability (SAT) problem. Second, we show that verifying robustness under non-uniform image occlusion is NP-complete through a reduction from SAT. Finally, we demonstrate that uniform occlusion induces a piecewise-constant structure in the network output, which enables the design of a polynomial-time algorithm for robustness verification.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 3 of its 4 references that are in the map. First posted on arXiv 17 Jun 2026.

Builds on

3 of 4 references.

References · 3

  1. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
  2. 2017Verifying Properties of Binarized Deep Neural Networkscited by 79
  3. 2023OccRob: Efficient SMT-Based Occlusion Robustness Verification of Deep Neural Networkscited by 5

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization
  2. 2025On Integer Programming for the Binarized Neural Network Verification Problem
  3. 2022A Mixed Integer Programming Approach for Verifying Properties of Binarized Neural Networks
  4. 2021BDD4BNN: A BDD-based Quantitative Analysis Framework for Binarized Neural Networks
  5. 2025Efficient Certified Reasoning for Binarized Neural Networks
  6. 2023ARBiBench: Benchmarking Adversarial Robustness of Binarized Neural Networks
  7. 2026Scalable Digital Compute-in-Memory Ising Machines for Robustness Verification of Binary Neural Networks
  8. 2022Lipschitz Continuity Retained Binary Neural Network