A Phase Transition and Quadratic Time Estimator for Network Reliability

Explore a groundbreaking approach to network reliability estimation in this 32-minute conference talk presented at the Association for Computing Machinery (ACM). Delve into the recent history of network reliability and discover a novel Õ(n) runtime method for unbiased estimators. Examine the limitations of naive Monte Carlo techniques and learn about a different estimator that offers improved performance. Gain insights into the general approach, key definitions, and the crucial role of pairability Xc(p) in the estimation process. Understand the concept of q-relative variance and its significance in near-independence scenarios. Investigate paired failures and cut bounds using contraction algorithms. Analyze the phase transition phenomenon and its impact on small cuts. Conclude with a summary of the algorithm and explore intriguing conjectures in the field of network reliability estimation.

Network Reliability
Recent History
This Work: Õ(n) Runtime
Unbiased Estimators
Naive Monte Carlo
A Different Estimator
General Approach
Definitions
Role of Pairability Xc(p)
Why q- Relative Variance?
Near-Independence
Paired Failures
Cut (Pair) Bounds by Contraction Algorithm
The Phase Transition
Small Cuts
Summary: Algorithm
Conjectures