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.