Please note: This seminar will take place in DC 1304 and online.
Robert Wang, PhD candidate
David R. Cheriton School of Computer Science
Recently, sharp matrix concentration inequalities were developed using the theory of free probability. These results lead to a powerful a new framework for analyzing random matrices, with many applications in algorithm analysis, statistical inference, and graph theory.
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 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.
To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.