Network Unreliability in Sub-quadratic Time
13Debmalya Panigrahi (Duke University)
https://simons.berkeley.edu/talks/debmalya-panigrahi-duke-university-2023-12-01
Optimization and Algorithm Design
The (all-terminal) network unreliability problem asks for an estimation of the probability that a given network disconnects when every edge fails independently with a given probability. As one of the original #P-hard problems, the focus over the last three decades has been on designing progressively faster fully polynomial-time approximation schemes (FPTAS). In this talk, I will present a new algorithm for this problem that runs in almost m+n^{1.5} time. This improves the previous best running time of nearly n^2 (Karger, STOC 2020) and breaches a qualitative barrier of enumerating all n^2 min-cuts that applied to all previous algorithms for this problem.
This is joint work with Ruoxu Cen (Duke), William He (Duke), and Jason Li (Simons Institute).