Theory Seminar: Please join us on April 21st at 11:00 AM for a talk by Robert Wang from the University of Waterloo, titled “Spectral Sparsification by Deterministic Discrepancy.”. The talk will be given exclusively on Zoom: https://illinois.zoom.us/j/84700567676?pwd=SG96MlRZT3M0N0paTGFYeEljL2hhUT09
Please see the abstract below:
Abstract: Spectral sparsification and discrepancy minimization are two well-studied areas that are closely related. Building on recent connections between these two areas, we generalize the “deterministic discrepancy walk” framework by Pesenti and Vladu [SODA 23] for vector discrepancy to matrix discrepancy, and use it to give a simpler proof of the matrix partial coloring theorem of Reis and Rothvoss [SODA 20]. Moreover, we show that this matrix discrepancy framework provides a unified approach for various spectral sparsification problems, from stronger notions including unit-circle approximation and singular value approximation to weaker notions including graphical spectral sketching and effective resistance sparsification. In all of these applications, our framework produces improved results with a simpler and deterministic analysis.