{"ID":23475059,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19794","arxiv_id":"2609.19794","title":"Polynomial Time Algorithms for the Kadison-Singer Problem","abstract":"Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions. We provide polynomial-time algorithms for the Kadison--Singer problem. For Hermitian matrices $A_1,\\ldots,A_m\\in\\mathbb C^{n\\times n}$ of rank at most one, we give two algorithms that find signs $σ\\in\\{\\pm1\\}^m$ satisfying $\\|\\sum_i σ_iA_i\\|\\le C\\|\\sum_i A_i^2\\|^{1/2}$. The deterministic algorithm achieves $C=3.3443$ using $\\widetilde O(mn^2+n^{56})$ arithmetic operations. The randomized algorithm achieves $C=4.8628$ using $\\widetilde O(mn^2+n^{5.88})$ arithmetic operations in expectation. For vectors satisfying $\\sum_i a_ia_i^*=I$ and $\\|a_i\\|^2\\leα$, the algorithms yield partitions $[m]=I_1\\cup I_2$ satisfying $\\|\\sum_{i\\in I_j}a_ia_i^*-I/2\\|\\le (C/2)\\sqrtα$ for $j=1,2$.","short_abstract":"Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions. We provide polynomial-time algorithms for the Kadison--Singer problem. For Hermitian matrices $A_1,\\ldots,A_m\\in\\mathbb C^{n\\times n}$ of rank at most one, we give two algorithms that find signs $σ\\in\\{\\pm1\\}^m$ satisfying...","url_abs":"https://arxiv.org/abs/2609.19794","url_pdf":"https://arxiv.org/pdf/2609.19794v1","authors":"[\"Zhao Song\",\"Song Yue\"]","published":"2026-09-17T07:00:27Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}