Title: Fault-Tolerant Reachability and Strong-connectivity Structures

Description: Speaker: Dr. Keerti Choudhary

Time: Monday, 14 October 2019, 10:30am
Venue: Dept. of CSE, Room no. 109, 01st Floor, New CSE/CC Bldg.


Abstract:
Reachability and strong-connectivity are some of the fundamental graph problems. In the static setting, both problems can be solved in O(m+n) time for any directed graph G with n vertices and m edges. However, most real-world networks are prone to failures. The failures are transient and occur for a small duration of time. Under such a setting, we would like to preprocess the graph to compute data-structures that can achieve robustness by being functional even after the occurrence of failures. In recent years, researchers have studied various questions pertaining to connectivity, distances, routing, min-cuts, etc. in the domain of fault tolerance networks.

In this talk, I will discuss the following questions:
1. Can we compute a reachability tree in just linear time, after the
occurrence of a small number of failures?
2. How fast can we compute the strongly connected components,
again on the occurrence of failures?
3. Does there exist a sparse certificate for these structures that
remains valid even after a bounded number of failures?

The solutions to these problems employ extremely basic tools like max-flows, min-cuts, and heavy-path-decomposition.


Speaker Profile:
Keerti Choudhary is currently a postdoc at Weizmann Institute of Science. She works in the area of Algorithms, particularly dynamic and fault-tolerant graph algorithms, Combinatorics, and Graph theory. She finished her PhD. in 2017 at IIT Kanpur. She is the recipient of the ACM India Doctoral Dissertation Award 2019 and the IBM Outstanding Ph.D. Thesis Award at IIT Kanpur for the year 2016-17.

Organization:
Weizmann Institute of Science



Host:
Prof. Rohit Gurjar

Date: Monday, 14 October, 2019
Time: 10:30am IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Sunday, 10 November, 2019 1:21pm IST
Send Reminder: Yes  -  232 hours 29 minutes before start
Participants: Department Calendar
<office@cse.iitb.ac.in> (External User)
_NUC_department <all@cse.iitb.ac.in> (External User)