The Price of Privacy For Approximating Max-CSP
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912893682843648 |
|---|---|
| author | Dharangutte, Prathamesh Liu, Jingcheng Manurangsi, Pasin Rafiey, Akbar Vajanopath, Phanu Zou, Zongrui |
| author_facet | Dharangutte, Prathamesh Liu, Jingcheng Manurangsi, Pasin Rafiey, Akbar Vajanopath, Phanu Zou, Zongrui |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_09273 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Price of Privacy For Approximating Max-CSP Dharangutte, Prathamesh Liu, Jingcheng Manurangsi, Pasin Rafiey, Akbar Vajanopath, Phanu Zou, Zongrui Data Structures and Algorithms Cryptography and Security 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. |
| title | The Price of Privacy For Approximating Max-CSP |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2602.09273 |