Video of this talk is available at: https://smartech.gatech.edu/handle/1853/55915

Full collection of talk videos are available at: https://smartech.gatech.edu/handle/1853/46836**Algorithms & Randomness Center (ARC)**

**Monday, September 26, 2016
Klaus 1116 East - 11:00 am**

**Title:**

A Fast and Simple Unbiased Estimator for Network (Un)reliability

**Abstract**:

The following procedure yields an unbiased estimator for the disconnection probability of an n-vertex graph with minimum cut c if every edge fails independently with probability p: (i) contract every edge independently with probability 1-n^{-2/c}, then (ii) recursively compute the disconnection probability of the resulting tiny graph if each edge fails with probability n^{2/c}p. We give a short, simple, self-contained proof that this estimator can be computed in linear time and has relative variance O(n^2). Combining these two facts with a relatively standard sparsification argument yields an O(n^3\log n)-time algorithm for estimating the (un)reliability of a network. We also show how the technique can be used to create unbiased samples of disconnected networks.

Speaker's webpage: http://people.csail.mit.edu/karger/

Fall 2016 ARC Seminar Schedule: http://arc.gatech.edu/node/114