{"id":"arxiv/2611.18650","url":"https://arxiv.org/abs/2611.18650","tags":["cond-mat.dis-nn","cs.IT","cs.LG","math.PR"],"score":0,"title":"Random matrix discrepancy -- CLuP algorithm and parametric RDT approach","domain":"cond-mat.dis-nn","source":"arxiv","authors":["Mihailo Stojnic"],"reviews":0,"subject":"cond-mat.dis-nn","summary":"We study information-theoretic and algorithmic aspects of random matrix discrepancy in proportional regime. The problem amounts to finding $κ=\\min_{\\x\\in\\mB^n}\\|\\sum_{i=1}^{n}\\bar{A}_i\\x_i\\|_2$, where $\\bar{A}_i\\in\\mR^{d\\times d}$ is a collection of $n$ iid GOE matrices, $\\mB^n$ are vertices of the unit cube in $\\mR^n$, and $α=\\lim_{n\\rightarrow \\infty}\\frac{n}{d^2}$ is a proportionality constant. Strong progress is made in several directions: (i) We develop a Random duality theory (RDT) framework and utilize its a lifted variant to establish lower bounds on $κ$, which precisely match the…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}