{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiejrdozkfxubbap5pzfh54fw6v7fjezradc67uedu6wfnbqgr54v4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnespjn4dsn2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.03807v1",
  "publishedAt": "2026-06-03T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Marco Benedetti",
    "Andrej Bogdanov",
    "Enrico M. Malatesta",
    "Marc Mézard",
    "Gianmarco Perrupato",
    "Alon Rosen",
    "Nikolaj I. Schwartzbach",
    "Riccardo Zecchina"
  ],
  "textContent": "**Authors:** Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc Mézard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, Riccardo Zecchina\n\nWe initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix $\\mathbf{A} \\in \\mathbb{R}^{m\\times n}$, an input $\\mathbf{x} \\in \\\\{-1,1\\\\}^n$ is mapped to a binary output vector $\\varphi(\\mathbf{A}\\mathbf{x})\\in \\\\{-1,1\\\\}^m$, where $\\varphi$ is an activation function with constant behavior on $[κ, \\infty)$ for some threshold $κ\\geq 0$. We identify the threshold scale $κ=Θ(1/\\sqrtα)$, where $α=m/n$, as separating two complementary phenomena. When $κ\\ll 1/\\sqrtα$, we give a simple online algorithm that efficiently produces extensive collisions. When $κ\\gg 1/\\sqrtα$, for a natural \\emph{randomized} non-periodic activation and suitable oscillation complexity, we prove that the extensive-collision space exhibits an overlap gap property (OGP), yielding an exponential lower bound against online algorithms. Ours is the first work to use the overlap gap property as a rigorous criterion for collision resistance. The key difference between collision finding and average-case search is that collision finding has a new ``worst-case'' aspect: the collision finder has full control over the choice of colliding pairs. Our lower bound is proved in the online model; extending such guarantees to broader classes of algorithms, including spectral, algebraic, lattice-based, or quantum methods, remains an open direction.",
  "title": "Collision Resistance of Single-Layer Neural Nets"
}