Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds
TL;DR
This work generalizes the implicit representation framework of Gupta et al. (SODA 2010) by allowing the encoder to run in fixed-parameter tractable time, and provides representation-dependent lower bounds that hold even for larger $\epsilon$.
Abstract
We study combinatorial optimization problems under the constraint of $\epsilon$-differential privacy ($\epsilon$-DP). Given the strong lower bounds for explicitly outputting solutions, we work within the implicit representation framework of Gupta et al. (SODA 2010), where a private polynomial-time randomized"encoder"generates a representation of a solution, and a"decoder"uses this representation along with the input to extract a valid final solution. In this work, we generalize this framework by allowing the encoder to run in fixed-parameter tractable time. This circumvents approximation barriers inherent to polynomial-time algorithms and obtains improved guarantees for many fundamental combinatorial optimization problems. Finally, we establish the first representation-independent lower bounds for our framework. Assuming a non-uniform variant of the Gap Exponential Time Hypothesis, for sufficiently small $\epsilon>0$, we prove that no $\epsilon$-DP encoder-decoder pair can achieve certain approximation guarantees, if the decoder runs in subexponential time. We further provide representation-dependent lower bounds that hold even for larger $\epsilon$.