{"ID":3004734,"CreatedAt":"2026-06-03T03:09:48.883664427Z","UpdatedAt":"2026-06-05T11:43:53.432517148Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.03807","arxiv_id":"2606.03807","title":"Collision Resistance of Single-Layer Neural Nets","abstract":"We 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.","short_abstract":"We 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 a...","url_abs":"https://arxiv.org/abs/2606.03807","url_pdf":"https://arxiv.org/pdf/2606.03807v1","authors":"[\"Marco Benedetti\",\"Andrej Bogdanov\",\"Enrico M. Malatesta\",\"Marc Mézard\",\"Gianmarco Perrupato\",\"Alon Rosen\",\"Nikolaj I. Schwartzbach\",\"Riccardo Zecchina\"]","published":"2026-06-02T15:52:45Z","proceeding":"cs.CR","tasks":"[\"cs.CR\",\"cs.CC\"]","methods":"[]","has_code":false}