The Price of Privacy For Approximating Max-CSP

We study approximation algorithms for Maximum Constraint Satisfaction Problems (Max-CSPs) under differential privacy (DP) where the constraints are considered sensitive data. Information-theoretically, we aim to classify the best approximation ratios possible for a given privacy budget $\epsilon$. In the high-privacy regime ($\epsilon \ll 1$), we show that any $\epsilon$-DP algorithm cannot beat a random assignment by more than $O(\epsilon )$ in the approximation ratio. We devise a polynomial-time algorithm which matches this barrier under the assumptions that the instances are bounded-degree and triangle-free. Finally, we show that one or both of these assumptions can be removed for specific CSPs–such as Max-Cut or Max $k$-XOR–albeit at the cost of computational efficiency.