Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $3.37\,\|\sum_i \mathrm{Tr}(A_i)A_i\|^{1/2}$. This yields Kadison--Singer half-partitions with error below $1.69\sqrt{\varepsilon}$, as well as deterministic graph signings that control signed adjacency and signed degrees simultaneously. The proof builds on the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.23855
curl -X POST /api/v1/records/arxiv/2609.23855/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.23855/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'