Conference paper
Topological Data Analysis on Noisy Quantum Computers
Ismail Akhalwaya, Shashanka Ubaru, et al.
ICLR 2024
We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log 2 n) factor in (m + n 3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time (m + n 2). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log 2 n)-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time. © 2009 ACM.
Ismail Akhalwaya, Shashanka Ubaru, et al.
ICLR 2024
Amarachi Blessing Mbakwe, Joy Wu, et al.
NeurIPS 2023
P.C. Yue, C.K. Wong
Journal of the ACM
Saurabh Paul, Christos Boutsidis, et al.
JMLR