Algorithms Seminar

Hypergraph Unreliability in Quasi-Polynomial Time

April 25, -
Speaker(s): Ruoxu Cen


The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the unreliability problem has been studied over many decades, and multiple fully polynomial-time approximation schemes are known starting with the work of Karger (STOC 1995). In contrast, prior to this work, no non-trivial result was known for hypergraphs (of arbitrary rank).

Speaker Bio

Ruoxu Cen is a fourth-year Ph.D. student at Duke University.  His research interest is graph algorithms of theoretical computer science. He is advised by Prof. Debmalya Panigrahi. His recent work has been focusing on a wide variety of problems related to minimum cuts.

Zoom Link



Yiheng Shen