Yuichi Yoshida (National Institute of Informatics, Japan)
Approximation vs Sensitivity: Stable Algorithms Under Input Perturbations
Abstract
Traditional approximation algorithms are judged by running time and approximation ratio, usually assuming a fixed input. In modern applications, however, data are noisy and evolving, and algorithms support explanation, reproducibility, and high-stakes decisions. If tiny input changes can drastically alter the output, we cannot trust or debug them. Sensitivity formalizes this by asking how much an algorithm's output can change when we modify a single input element, typically measured in Hamming distance between outputs.
Average sensitivity instead looks at the expected Hamming distance under a random perturbation. This tutorial introduces these notions and emphasizes the trade-off between approximation quality and sensitivity. I will survey recent upper and lower bounds, and connections to other computational models, including how sensitivity lower bounds can be turned into lower bounds for distributed algorithms.
Biography
Yuichi Yoshida is a Professor at the National Institute of Informatics (NII), where he has served as Assistant Professor (2012-2015), Associate Professor (2015-2022), and Professor (since 2022). He received his Ph.D. in Informatics from Kyoto University in 2012. His research lies in theoretical computer science, with a focus on sublinear-time algorithms, spectral graph theory, and algorithmic stability, as well as more applied work on large-scale network algorithms. He has received several honors, including an AISTATS Best Paper Award, the Microsoft Research Award (IPSJ), the MEXT Young Scientists' Prize, and the JSPS Ikushi Prize.