Spectral Sparsification by Deterministic Discrepancy Walk
<|reference_start|>Spectral Sparsification by Deterministic Discrepancy Walk: 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.<|reference_end|>
@article{lau2024spectral,
    title={Spectral Sparsification by Deterministic Discrepancy Walk},
    author={Lap Chi Lau, Robert Wang, Hong Zhou},
    journal={arXiv preprint arXiv:2408.06146},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.06146},
    primaryClass={cs.DS math.CO}
}