Results 1811 - 1820 of 23856

Title: An LCA for Greedy Set Cover
 

Abstract: We study the Set Cover problem in the setting of Local Computation (LCAs). In the classical setting, the Set Cover problem is known to have simple linear-time algorithms in two regimes of approximation: (i) a $1 + \ln n$-approximate algorithm and (ii) an $f$-approximate algorithm.
While efficient LCAs achieving $O(f)$-approximations with $\text{poly}(\Delta, f)$ queries follow from prior work – [Kapralov, Mitrovic, Norouzi-Fard, Tardos SODA ‘20] and [Ghaffari FOCS ‘22], the state-of-art algorithm achieving $O(\log \Delta)$ approximation –  [Grunau, Mitrovic, Rubinfeld, Vakilian SODA ‘20] – requires exponential in $\log^2 \Delta + \log \Delta \log f$ queries. All of these algorithms are derived from distributed algorithms for these problems. They can be interpreted as sparsifying the input graph so that the corresponding distributed algorithm has a similar output. We show that a simple pruning procedure can sparsify the input instance so that its “average degree” is at most $O(\log \Delta \log f)$. With a slightly more involved procedure, it can also be reduced to a constant. Our procedure reduces the exponent of the state-of-the-art to $\tilde{O}(\log \Delta \log f)$ and $\log \Delta \log f$ respectively.

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 sensitivity have been developed for many problems, no sensitivity lower bounds were previously known for approximation algorithms. In this work, we establish the first polynomial lower bound on the sensitivity of (randomized) approximation algorithms for constraint satisfaction problems (CSPs) by adapting the probabilistically checkable proof (PCP) framework to preserve sensitivity lower bounds. From this, we derive polynomial sensitivity lower bounds for approximation algorithms for a variety of problems, including maximum clique, minimum vertex cover, and maximum cut. Given the connection between sensitivity and distributed algorithms, our sensitivity lower bounds also allow us to recover various round complexity lower bounds for distributed algorithms in the LOCAL model. Additionally, we present new lower bounds for distributed CSPs.

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.

No abstract available.

Differential privacy has become one of the frequently applied techniques in the development of randomized estimation algorithms that are resistant to adaptive updates and queries. This heavily relies on the fact that it is possible to take estimates from several copies of the randomized algorithm and obscure them by returning their private median. This approach does not easily translate to a setting in which the algorithm returns not just an estimate but a specific object from a given set. As opposed to estimates, there is no obvious method for outputting a private aggregate of several samples from the set of valid answers, which in this case is supposed to be an element of the set as well. We focus on the nearest neighbor search problem via Locality Sensitive Hashing. This problem has recently been showed to be vulnerable to the adaptive queries. We demonstrate various techniques that can be used to make its output adversarially robust.