Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
Abstract
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 |∑i Tr(Ai)Ai|1/2. This yields Kadison--Singer half-partitions with error below 1.69√ε, as well as deterministic graph signings that control signed adjacency and signed degrees simultaneously. The proof builds on the spectral-potential method of Ezeunala and Jiang (2026) and introduces a new way to choose rounding directions. We prove polynomial bit complexity for the rounding procedure. Second, we give a Las Vegas algorithm for the Bilu--Linial signing problem on an arbitrary prescribed graph. If G has n vertices and maximum degree Δ≥3, the algorithm terminates almost surely. It uses fewer than 100n3 insertion attempts in expectation and returns a signing with |As|<2√(2(Δ−1)). For bipartite graphs its one-sided form gives the sharp universal bound |As|<2√(Δ−1). The algorithm builds the signing by inserting vertices and recursively deleting and restoring neighbors after rejected insertions. In the analysis, the √2 gap to the Bilu--Linial conjecture comes from a factor of two in the bound for vertex deletions in the two-sided case. On a d-regular bipartite Ramanujan base the same signing produces a Ramanujan $2$-lift of that prescribed base.
Related
- Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
- A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
- Orthogonal and unitary signings of cube-like graphs
- A 3-regular counterexample to the Bilu--Linial signing conjecture
BibTeX
@misc{jadbabaie2026kadisonsinger,
title = {{Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time}},
author = {Ali Jadbabaie and Amin Saberi and Suvrit Sra},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23855},
eprint = {2609.23855},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23855},
}
RIS
TY - UNPB
TI - Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
AU - Ali Jadbabaie
AU - Amin Saberi
AU - Suvrit Sra
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23855
UR - https://arxiv.org/abs/2609.23855
AB - 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 |∑_i Tr(A_i)A_i|^1/2. This yields Kadison--Singer half-partitions with error below 1.69√ε, as well as deterministic graph signings that control signed adjacency and signed degrees simultaneously. The proof builds on the spectral-potential method of Ezeunala and Jiang (2026) and introduces a new way to choose rounding directions. We prove polynomial bit complexity for the rounding procedure. Second, we give a Las Vegas algorithm for the Bilu--Linial signing problem on an arbitrary prescribed graph. If G has n vertices and maximum degree Δ≥3, the algorithm terminates almost surely. It uses fewer than 100n^3 insertion attempts in expectation and returns a signing with |A_s|<2√(2(Δ−1)). For bipartite graphs its one-sided form gives the sharp universal bound |A_s|<2√(Δ−1). The algorithm builds the signing by inserting vertices and recursively deleting and restoring neighbors after rejected insertions. In the analysis, the √2 gap to the Bilu--Linial conjecture comes from a factor of two in the bound for vertex deletions in the two-sided case. On a d-regular bipartite Ramanujan base the same signing produces a Ramanujan $2$-lift of that prescribed base.
ER -