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 $\ddot{I}†(\mathbf{Ax})\in \{-1,1{\}}^m$, where $\ddot{I}†$ is an activation function with constant behavior on $[\hat{I}º,\infty )$ for some threshold $\hat{I}º\ge 0$. We identify the threshold scale $\hat{I}º=\hat{I}˜(1/\sqrt{\hat{I}}\pm )$, where $\hat{I}\pm =m/n$, as separating two complementary phenomena. When $\hat{I}º\ll 1/\sqrt{\hat{I}}\pm$, we give a simple online algorithm that efficiently produces extensive collisions. When $\hat{I}º\gg 1/\sqrt{\hat{I}}\pm$, 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.