ARC Colloquium: David Karger (MIT)

Event Details

Dani Denton

denton at cc dot gatech dot edu


Summary Sentence: A Fast and Simple Unbiased Estimator for Network (Un)reliability (Klaus 1116 E at 11am)

Full Summary: No summary paragraph submitted.

Video of this talk is available at:

Full collection of talk videos are available at:

Algorithms & Randomness Center (ARC)

David Karger - MIT

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

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

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:
Fall 2016 ARC Seminar Schedule:


Additional Information

In Campus Calendar

ARC, School of Computer Science

Invited Audience
Faculty/Staff, Public, Undergraduate students, Graduate students
Algorithm and Randomness Center, ARC, Computational Complexity, Computational Learning Theory, Georgia Tech
  • Created By: Dani Denton
  • Workflow Status: Published
  • Created On: Aug 8, 2016 - 6:29am
  • Last Updated: Apr 13, 2017 - 5:15pm