{"id":"arxiv/2611.03397","url":"https://arxiv.org/abs/2611.03397","tags":["cs.CC","cs.DS","math-ph","math.PR"],"score":0,"title":"Online Algorithms Cannot Find Isolated Perceptron Solutions","domain":"cs.CC","source":"arxiv","authors":["Shuangping Li","Gabe Schoenbach"],"reviews":0,"subject":"cs.CC","summary":"The binary perceptron problem asks for a length-$n$ sign vector in the intersection of $\\lfloor αn\\rfloor$-many independent random Gaussian half-spaces. A striking feature of this model is strong freezing: at every constraint density $α> 0$, all but a vanishing fraction of solutions are isolated -- $Ω(n)$-far from all others, in Hamming distance. Such solutions are believed to be algorithmically inaccessible. Nevertheless, efficient algorithms find solutions at some constraint densities $α$. One possible resolution of this apparent contradiction is that the solution space also contains rare…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}