The Price of Privacy For Approximating Max-CSP

arXiv:2602.09273v1 Announce Type: new
Abstract: 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 $varepsilon$. In the high-privacy regime ($varepsilon ll 1$), we show that any $varepsilon$-DP algorithm cannot beat a random assignment by more than $O(varepsilon)$ 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.