{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreieibiuy5uza34j5hy6tedbkyblfqt3lqimlnt6tktv3zuwxzan3re",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3miidx5yhnug2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.00328v1",
  "publishedAt": "2026-04-02T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Shuyang Gong",
    "Brice Huang",
    "Shuangping Li",
    "Mark Sellke"
  ],
  "textContent": "**Authors:** Shuyang Gong, Brice Huang, Shuangping Li, Mark Sellke\n\nWe study the binary perceptron, a random constraint satisfaction problem that asks to find a Boolean vector in the intersection of independently chosen random halfspaces. A striking feature of this model is that at every positive constraint density, it is expected that a $1-o_N(1)$ fraction of solutions are \\emph{strongly isolated}, i.e. separated from all others by Hamming distance $Ω(N)$. At the same time, efficient algorithms are known to find solutions at certain positive constraint densities. This raises a natural question: can any isolated solution be algorithmically visible? We answer this in the negative: no algorithm whose output is stable under a tiny Gaussian resampling of the disorder can \\emph{reliably} locate isolated solutions. We show that any stable algorithm has success probability at most $\\frac{3\\sqrt{17}-9}{4}+o_N(1)\\leq 0.84233$. Furthermore, every stable algorithm that finds a solution with probability $1-o_N(1)$ finds an isolated solution with probability $o_N(1)$. The class of stable algorithms we consider includes degree-$D$ polynomials up to $D\\leq o(N/\\log N)$; under the low-degree heuristic \\cite{hopkins2018statistical}, this suggests that locating strongly isolated solutions requires running time $\\exp(\\widetildeΘ(N))$. Our proof does not use the overlap gap property. Instead, we show via Pitt's correlation inequality that after a random perturbation of the disorder, the number of solutions located close to a pre-existing isolated solution cannot concentrate at $1$.",
  "title": "Stable algorithms cannot reliably find isolated perceptron solutions"
}