2 papers
cs.DS2026
Non-Signaling Locality Lower Bounds for Dominating Set
Noah Fleming, Max Hopkins, Yuichi Yoshida
Minimum dominating set is a basic local covering problem and a core task in distributed computing. Despite extensive study, in the classic LOCAL model there exist significant gaps…
cs.DS2025
Sensitivity Lower Bounds for Approximaiton Algorithms
Noah Fleming, Yuichi Yoshida
Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitiv…