Derandomizing Matrix Concentration Inequalities from Free Probability
Provides the first deterministic polynomial-time algorithms for two important problems in combinatorial optimization and graph theory, demonstrating the computational utility of free probability theory.
This work designs polynomial-time deterministic algorithms to achieve guarantees of sharp matrix concentration inequalities from free probability, yielding deterministic algorithms for the matrix Spencer problem and near-Ramanujan graph construction.
Recently, sharp matrix concentration inequalities~\cite{BBvH23,BvH24} were developed using the theory of free probability. In this work, we design polynomial time deterministic algorithms to construct outcomes that satisfy the guarantees of these inequalities. As direct consequences, we obtain polynomial time deterministic algorithms for the matrix Spencer problem~\cite{BJM23} and for constructing near-Ramanujan graphs. Our proofs show that the concepts and techniques in free probability are useful not only for mathematical analyses but also for efficient computations.