3 papers
cs.DS2026
Decisive Margins in Differentially Private Voting
Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn +1
Differential privacy protects individual voting records by injecting randomness into the published outcome, but this noise can lead to erroneous results when an election is close.…
cs.DS2026
The Price of Privacy For Approximating Max-CSP
Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi +3
We study approximation algorithms for Maximum Constraint Satisfaction Problems (Max-CSPs) under differential privacy (DP) where the constraints are considered sensitive data. Infor…
cs.DS2025
Improved Differentially Private Algorithms for Rank Aggregation
Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn +1
Rank aggregation is a task of combining the rankings of items from multiple users into a single ranking that best represents the users' rankings. Alabi et al. (AAAI'22) presents di…