{"id":"arxiv/2610.01591","url":"https://arxiv.org/abs/2610.01591","tags":["cs.DS","cs.CC","cs.DM","math.CO","math.PR"],"score":0,"title":"Stable and Online Algorithms for Random Matrix Discrepancy","domain":"cs.DS","source":"arxiv","authors":["Eren C. Kızıldağ","Shuangping Li"],"reviews":0,"subject":"cs.DS","summary":"We study the average-case matrix discrepancy problem: given independent normalized $d\\times d$ Gaussian orthogonal ensemble matrices $A_1,\\dots,A_N$ and a fixed margin $κ>0$, find signs $σ_1,\\dots,σ_N\\in\\{-1,1\\}$ such that the operator norm of $\\sum_{i=1}^N σ_i A_i$ is at most $κ\\sqrt{N}$. Focusing on the proportional regime $N/d^2\\to τ\\in(0,\\infty)$ as $d\\to\\infty$ followed by the small-margin limit $κ\\downarrow 0$, we characterize the density required by stable offline algorithms and by online algorithms. In the offline setting, we construct a polynomial-time \\emph{recenter-and-round}…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}