Differential privacy achieves better algorithms using parameter tractability
Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds
Data Structures and AlgorithmsCryptography and Security
Summary
Many optimization problems need to keep data private, but doing this often makes finding good solutions very hard or slow. The authors show how allowing the privacy algorithm to run using a special way that focuses on certain parameters helps find better solutions more efficiently. They also prove limits on how well any such private method can work under reasonable assumptions, even if the method is very powerful. This gives clearer guidance on what is possible when combining privacy and complex problem solving.
What this means in practice
- •For data privacy engineers: Create private data handling algorithms that improve optimization quality by focusing computation on key parameters within practical time.
- •For complexity theorists: Use established lower bounds to rule out the existence of faster private encoders achieving certain approximation goals under strong complexity assumptions.
A theory result. No direct application yet.
Authors
Pritish Kamath, Ravi Kumar, Pasin Manurangsi
Abstract
We study combinatorial optimization problems under the constraint of $ε$-differential privacy ($ε$-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 $ε> 0$, we prove that no $ε$-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 $ε$.