View all Seminars  |  Download ICal for this event

Average Sensitivity of Graph Algorithms

Series: Theory Seminar

Speaker: Prof. Yuichi YoshidaAssociate ProfessorNational Institute of InformaticsJapan

Date/Time: Jul 15 11:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

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. Hence, it is desirable to use algorithms that, even when provided with only a subgraph that misses a few edges, output solutions that are close to the solutions output when the whole graph is available. We formalize this feature by introducing the notion of average sensitivity of graph algorithms, which is the average earth movers distance between the output distributions of an algorithm on a graph and its subgraph obtained by removing an edge, where the average is over the edges removed and the distance between two outputs is the Hamming distance.
In this work, we initiate a systematic study of average sensitivity. After deriving basic properties of average sensitivity such as composition, we provide efficient approximation algorithms with low average sensitivities for concrete graph problems, including the minimum spanning for- est problem, the global minimum cut problem, the minimum s-t cut problem, and the maximum matching problem. One of the main ideas involved in designing our algorithms with low average sensitivity is the following fact; if the presence of a vertex or an edge in the solution output by an algorithm can be decided locally, then the algorithm has a low average sensitivity, allowing us to reuse the analyses of known sublinear-time algorithms and local computation algorithms.
Microsoft teams link:

Speaker Bio:

Host Faculty: Dr. Anand Louis