{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigba5n5vmn4ncqdnq25b65wgrrgj2ufnlqjycjjf2hpfc3pdcc5xa",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3moksjjvxjcy2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.18918v1",
  "publishedAt": "2026-06-18T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Harshit Goyal",
    "Sudakshina Dutta"
  ],
  "textContent": "**Authors:** Harshit Goyal, Sudakshina Dutta\n\nThis 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.",
  "title": "Some Complexity Results for Robustness Verification for Binarized Neural Networks"
}