We study a new framework for designing differentially private (DP) mechanisms via randomized graph colorings, called rainbow differential privacy. In this framework, datasets are nodes in a graph, and two neighboring datasets are connected by an edge. Each dataset in the graph has a preferential ordering for the possible outputs of the mechanism, and these orderings are called rainbows. Different rainbows partition the graph of connected datasets into different regions. We show that if a DP mechanism at the boundary of such regions is fixed and it behaves identically for all same-rainbow boundary datasets, then a unique optimal $(\epsilon,\delta)$-DP mechanism exists (as long as the boundary condition is valid) and can be expressed in closed-form. Our proof technique is based on an interesting relationship between dominance ordering and DP, which applies to any finite number of colors and for $(\epsilon,\delta)$-DP, improving upon previous results that only apply to at most three colors and for $\epsilon$-DP. We justify the homogeneous boundary condition assumption by giving an example with non-homogeneous boundary condition, for which there exists no optimal DP mechanism.
- Home
- Search Results
- Page 1 of 1
Search for: All records
-
Total Resources5
- Resource Type
-
03000020000
- More
- Availability
-
41
- Author / Contributor
- Filter by Author / Creator
-
-
Sadeghi, Parastoo (5)
-
Johnson, Sarah (4)
-
Kliewer, Joerg (4)
-
Liu, Yucheng (4)
-
Ong, Lawrence (4)
-
Yeoh, Phee Lep (3)
-
D'Oliveira, Rafael_G L (1)
-
Gu, Yuzhou (1)
-
Günlü, Onur (1)
-
Lep Yeoh, Phee (1)
-
Médard, Muriel (1)
-
Schaefer, Rafael F (1)
-
Zhou, Ziqi (1)
-
#Tyler Phillips, Kenneth E. (0)
-
#Willis, Ciara (0)
-
& Abreu-Ramos, E. D. (0)
-
& Abramson, C. I. (0)
-
& Abreu-Ramos, E. D. (0)
-
& Adams, S.G. (0)
-
& Ahmed, K. (0)
-
- Filter by Editor
-
-
& Spizer, S. M. (0)
-
& . Spizer, S. (0)
-
& Ahn, J. (0)
-
& Bateiha, S. (0)
-
& Bosch, N. (0)
-
& Brennan K. (0)
-
& Brennan, K. (0)
-
& Chen, B. (0)
-
& Chen, Bodong (0)
-
& Drown, S. (0)
-
& Ferretti, F. (0)
-
& Higgins, A. (0)
-
& J. Peters (0)
-
& Kali, Y. (0)
-
& Ruiz-Arias, P.M. (0)
-
& S. Spitzer (0)
-
& Sahin. I. (0)
-
& Spitzer, S. (0)
-
& Spitzer, S.M. (0)
-
(submitted - in Review for IEEE ICASSP-2024) (0)
-
-
Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Free, publicly-accessible full text available June 24, 2025
-
Liu, Yucheng ; Ong, Lawrence ; Sadeghi, Parastoo ; Johnson, Sarah ; Kliewer, Joerg ; Yeoh, Phee Lep ( , IEEE Journal on Selected Areas in Information Theory)
-
Liu, Yucheng ; Ong, Lawrence ; Lep Yeoh, Phee ; Sadeghi, Parastoo ; Kliewer, Joerg ; Johnson, Sarah ( , 2022 IEEE International Symposium on Information Theory (ISIT))
-
Liu, Yucheng ; Ong, Lawrence ; Yeoh, Phee Lep ; Sadeghi, Parastoo ; Kliewer, Joerg ; Johnson, Sarah ( , 2021 IEEE Information Theory Workshop (ITW))
-
Liu, Yucheng ; Ong, Lawrence ; Johnson, Sarah ; Kliewer, Joerg ; Sadeghi, Parastoo ; Yeoh, Phee Lep ( , 2021 IEEE International Symposium on Information Theory (ISIT))