*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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/46836Algorithms & 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
