{"id":"arxiv/2609.18913","url":"https://arxiv.org/abs/2609.18913","tags":["cs.DS","math.FA"],"score":0,"title":"A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture","domain":"cs.DS","source":"arxiv","authors":["Tarun Kathuria"],"reviews":0,"subject":"cs.DS","summary":"\\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\\sqrt\\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}