arXiv preprint ·
Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
In brief
Privacy Meets Optimization: A New Approach
This paper introduces a novel framework that allows for the encoding of solutions in a way that respects differential privacy while also being fixed-parameter tractable. By doing so, it bypasses some of the approximation limits faced by previous methods.
What they found: The study shows that integrating differential privacy with fixed-parameter tractability can yield significant improvements in combinatorial optimization problems. It establishes new lower bounds, indicating that no encoder-decoder pair can achieve certain guarantees if the decoder runs in subexponential time. Overall, this framework enhances both privacy and solution quality in optimization tasks.
AI-written summary. Check anything you rely on against the original paper.
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 $ε$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
Prefix Sharing Is a Sorting Problem
Beyond Kruskal: Polynomial-Time Tensor Decomposition under the Lovitz-Petrov Condition
Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $β\leq \frac{1}{2}+\varepsilon$
Tight Hardness for Temporal Path Covers at Vertex-Cover Number Two
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.