{"id":"arxiv/2611.04294","url":"https://arxiv.org/abs/2611.04294","tags":["cs.DS","cs.CC","math.PR"],"score":0,"title":"State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron","domain":"cs.DS","source":"arxiv","authors":["Jianan Zhang","Shuangping Li"],"reviews":0,"subject":"cs.DS","summary":"The binary perceptron is a random constraint satisfaction problem that asks for a sign vector satisfying a system of random linear inequalities. Its solution space has a strikingly extreme geometry: at every positive constraint density, all but a vanishing fraction of the solutions are isolated. Yet polynomial-time algorithms find solutions at small enough constraint density, which raises the question of how efficient algorithms navigate such a landscape. Linear programming is a natural algorithm to study here, but its analysis has so far been limited to a single round. Li, Schramm, and Zhou…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}