Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

Ali Jadbabaie, Amin Saberi, Suvrit Sra

We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitr…