Theory Lunch Seminar - Ruoxu Chen

October 29, 2025 12:00pm — 1:00pm

Location:
In Person - Gates Hillman 8102

Speaker:
RUOXU CHEN , Ph.D. Student, Department of Computer Science, Duke University
https://sites.google.com/view/ruoxu-cen

Wednesday, October 29, 2025, 12 – 1pm 

The network unreliability problem asks for the probability that a given undirected graph gets disconnected when every edge independently fails with a given probability. Valiant (1979) showed that this problem is #P-hard; therefore, the best we can hope for are approximation algorithms. In a classic result, Karger (1995) obtained the first FPTAS for this problem by leveraging the fact that when a graph disconnects, it almost always does so at a near-minimum cut, and there are only a small (polynomial) number of near-minimum cuts. Since then, a series of results have obtained progressively faster algorithms to a quadratic-time algorithm (Karger, 2020). In a prior work (Cen, He, Li, and Panigrahi, 2024), we improved the running time to m^1+o(1) + Ô(n^3/2). In this talk, I will discuss our recent result that obtains an almost-linear time algorithm for the network unreliability problem. 

For More Information:
hfleisch@andrew.cmu.edu

Add event to Google
Add event to iCal