סמינר מחלקה אלגוריתמים ברשתות פרופ' דיוויד קרגר

26 ביוני 2022, 15:00 
Physical meeting (011 hall, Wolfson Building of Electrical Engineering-Kitot) 
סמינר מחלקה אלגוריתמים ברשתות פרופ' דיוויד קרגר

Fast and Simple Algorithms for All-Terminal Network Reliability

Speaker:    Prof. David Karger, EECS Department, MIT

Sunday, June 26, 2022

3:00-4:00pm

Room 011, Kitot Building

Abstract

The all-terminal network reliability problem asks to compute, for a given graph $G$, the probability that graph becomes disconnected when all edges fail independently with some probability.  This fundamental problem in graph theory and reliability has been studied for decades, with the first fully polynomial randomized approximation scheme (FPRAS) given in 1995.  

In this work, I will describe a particularly simple polynomial time algorithm for this problem, with an equally simple proof of correctness.  It relies on generating a low variance unbiased estimator using "partially sampled" graphs, then estimating their reliability recursively.  The resulting algorithm is far simpler and much faster than the first one.   The analysis introduces techniques that may be useful for a broader class of reliability problems.

I will then sketch more sophisticated techniques that can be used to improve the running time of this approximation scheme.  In particular I will show that as the edge failure probability decreases there is a rapid "phase transition" from a regime where the graph is likely disconnected, to one in which all cuts can be treated as failing independently which dramatically simplifies the problem.  The analysis relies on some new analysis of the Contraction Algorithm---a stochastic process of contracting randomly chosen graph edges until the graph has been fully collapsed.

Short Bio

David Karger (Ph.D. Stanford University 1994) is a professor of computer science in the EECS department at MIT, and a member of the Computer Science and Artificial Intelligence Laboratory.  His early research focused on randomized algorithms for graph optimization problems, and has since broadened to encompass information retrieval, databases, networking, natural language processing, coding theory, and human-computer interaction.  His work has won the SIGCOMM test of time award and the SIGIR test of time award.  He is a fellow of the ACM and of the American Academy of Arts and Sciences.

אוניברסיטת תל אביב עושה כל מאמץ לכבד זכויות יוצרים. אם בבעלותך זכויות יוצרים בתכנים שנמצאים פה ו/או השימוש
שנעשה בתכנים אלה לדעתך מפר זכויות, נא לפנות בהקדם לכתובת שכאן >>