Abstract

I will present our recent work on designing an efficient Local Computation Algorithm (LCA) for the set cover problem. The state-of-the-art LCA for computing an O(log Delta)-approximate set cover, developed by Grunau, Mitrović, Rubinfeld, and Vakilian (SODA 2020), achieves query complexity Delta^{O(log Delta)} x f^{O(log Delta * (log log Delta + log log f))}, where Delta is the maximum set size and f is the maximum frequency of any element across the sets. I will outline a new LCA that solves this problem using only f^{O(log Delta)} queries. In particular, for instances where f is polylogarithmic in Delta, our algorithm improves the query complexity from Delta^{O(log Delta)} to Delta^{O(log log Delta)}. Our central technical contribution is a new approach for designing LCAs that aggressively sparsifies the input instance while allowing for retroactive updates. Specifically, the algorithm occasionally "corrects" decisions made during earlier recursive calls. This mechanism enables stronger concentration guarantees, leading to a more efficient and sparser LCA execution. We believe that this retroactive sparsification technique may be of independent interest beyond the set cover problem. Joint work with Srikkanth Ramachandran, Ronitt Rubinfeld, and Mihir Singhal.