{"id":"arxiv/2609.17266","url":"https://arxiv.org/abs/2609.17266","tags":["cs.DS","cs.DM","math.CO","math.FA"],"score":0,"title":"Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer","domain":"cs.DS","source":"arxiv","authors":["Ekene Ezeunala","Haotian Jiang"],"reviews":0,"subject":"cs.DS","summary":"We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\\dots,H_N$ of rank at most one, finds signs $s\\in\\{\\pm1\\}^N$ with $\\|\\sum_i s_i H_i\\|\\le 13\\|\\sum_i H_i^2\\|^{1/2}$. As a corollary, for vectors $v_i$ with $\\sum_i v_iv_i^*=I$ and $\\|v_i\\|^2\\leδ$, the signs yield a partition $[N] = S_1 \\cup S_2$ such that each part satisfies $\\|\\sum_{i \\in S_j} v_i v_i^* - \\frac{I}{2}\\| \\leq \\frac{13}{2}\\sqrtδ$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}