Network Unreliability in Sub-quadratic Time
summary
New algorithm estimates all‑terminal network unreliability in roughly m + n^{1.5} time, improving over the previous ~n^2 bound and breaking the need to enumerate O(n^2) min‑cuts. It replaces inclusion–exclusion with a union‑bound surrogate z, samples cuts via recursive contraction + importance sampling, leverages spanning‑tree packing (Nash‑Williams/Tutte) and Gomory‑Hu style contractions, and treats the very reliable regime (u < n^{-3}) with a tailored estimator. The method is randomized, practical per the stated runtimes, and provably faster on worst‑case instances.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:40Defining network reliability
- 5:32Problem formalization
- 11:01Early research and complexity
- 16:51First generation algorithms
- 20:20Boolean formulas and truncation
- 29:25Second generation algorithms
- 37:26The quadratic barrier
- 44:38Third generation results
- 55:23Open questions and conclusion
related talks
24mAsymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
29mSynthesis of dependable and self-driving communication networks
46mA Framework for Imperfectly Observed Networks
16mUNUM: A New Framework for Network Control
17mNetHint: White-Box Networking for Multi-Tenant Data Centers
31mExpectAll: A BDD Based Approach for Link Failure Resilience in Elastic Optical Networks
18mGeminet: Learning the Duality-based Topology-Agnostic Update Operator for Lightweight...
16mScalable Tail Latency Estimation for Data Center Networks