Seminar Details

Graph Sparsification, first introduced in a seminal work of Benczur and Karger, and later developed by Spielman, Teng, Srivastava, and others, has proved to be an extremely versatile and useful tool in the field of graph algorithms, and more broadly, computer science as a whole. In this talk we consider the quantum version of graph sparsification, where we replace the (classical) cut predicate with the quantum-cut predicate, and ask the natural quantum-cut sparsification question. We prove that any graph admits a quantum-cut sparsifier of size O(n polylog(n)), thus proving a quantum generalization of Spielman-Srivastava sparsifiers. This is joint work with Joshua Brakensiek, Pravesh Kothari, and Aaron (Louie) Putterman, and the paper can be found here: https://arxiv.org/abs/2606.09728. No prior knowledge of quantum will be assumed, and everything will be defined as and when necessary.