Tata Institute of Fundamental Research
Average Sensitivity of Graph Algorithms
STCS Student Seminar
Speaker:
Nithin Varma (University of Haifa, Israel)
Organiser:
Neha Sangwan
Date:
Saturday, 8 Aug 2020, 16:00 to 17:00
Venue:
(Scan to add to calendar)
Abstract:
Abstract: In modern applications of graph algorithms, where the graphs of interest are large and dynamic, it is unrealistic to assume that an input representation contains the full information of a graph being studied. For example, consider a social network, where a vertex corresponds to a user and an edge corresponds to a friendship relation.
It is reasonable to assume that users do not always update new friendships on the social network, and that sometimes they do not fully disclose their friendship relations for security or privacy reasons.
This motivates the design of graph algorithms that, in spite of being given only a (large) subgraph as input, output solutions that are close to the solutions output when the whole graph is available. In this talk, I will introduce a notion of sensitivity of graph algorithms that formalizes this desirable feature. After discussing the basic properties of our sensitivity definition, I will give an overview of our main results, and present the key ideas used in the design of our algorithm with low sensitivity for the global minimum cut problem.
This is a joint work with Yuichi Yoshida.
| Speaker: | Nithin Varma (University of Haifa, Israel) |
| Organiser: | Neha Sangwan |
| Date: | Saturday, 8 Aug 2020, 16:00 to 17:00 |
| Venue: |
(Scan to add to calendar)
Abstract:
Abstract: In modern applications of graph algorithms, where the graphs of interest are large and dynamic, it is unrealistic to assume that an input representation contains the full information of a graph being studied. For example, consider a social network, where a vertex corresponds to a user and an edge corresponds to a friendship relation.
It is reasonable to assume that users do not always update new friendships on the social network, and that sometimes they do not fully disclose their friendship relations for security or privacy reasons.
This motivates the design of graph algorithms that, in spite of being given only a (large) subgraph as input, output solutions that are close to the solutions output when the whole graph is available. In this talk, I will introduce a notion of sensitivity of graph algorithms that formalizes this desirable feature. After discussing the basic properties of our sensitivity definition, I will give an overview of our main results, and present the key ideas used in the design of our algorithm with low sensitivity for the global minimum cut problem.
This is a joint work with Yuichi Yoshida.
It is reasonable to assume that users do not always update new friendships on the social network, and that sometimes they do not fully disclose their friendship relations for security or privacy reasons.
This motivates the design of graph algorithms that, in spite of being given only a (large) subgraph as input, output solutions that are close to the solutions output when the whole graph is available. In this talk, I will introduce a notion of sensitivity of graph algorithms that formalizes this desirable feature. After discussing the basic properties of our sensitivity definition, I will give an overview of our main results, and present the key ideas used in the design of our algorithm with low sensitivity for the global minimum cut problem.
This is a joint work with Yuichi Yoshida.