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 Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-10-15 Page: https://delphi.science/r/arxiv/2611.18650 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…