Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds
Theory paper combines differential privacy with fixed-parameter tractable encoders, improving approximation guarantees for combinatorial optimization and proving new lower bounds.
The paper studies combinatorial optimization under epsilon-differential privacy within the implicit encoder-decoder framework of Gupta et al. (SODA 2010), generalizing it to allow fixed-parameter tractable encoders. This circumvents approximation barriers inherent to polynomial-time algorithms and yields improved guarantees for fundamental combinatorial optimization problems. The authors establish the first representation-independent lower bounds: assuming a non-uniform variant of the Gap Exponential Time Hypothesis, no epsilon-DP encoder-decoder pair can achieve certain approximation guarantees with a subexponential-time decoder for sufficiently small epsilon. Representation-dependent lower bounds are also provided for larger epsilon.
- Extends private encoder-decoder framework with fixed-parameter tractable encoders
- Circumvents polynomial-time approximation barriers for DP optimization
- First representation-independent lower bounds under non-uniform Gap ETH
From the original article
1 min read at arxiv.orgWe 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.
By Pritish Kamath · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.