Extreme Points of the (0,δ)-LDP Polytope with Small Input Size and Arbitrary Output Sizes
Abstract
The structure of locally differentially private (LDP) mechanisms can be understood through the geometry of the corresponding privacy polytope. While the extreme points of the (ε,0)-LDP polytope are well characterized (Kairouz {et al.}, 2014; Holohan {et al.}, 2017), comparatively little is known for the (ε,δ)-LDP polytope with δ>0. Recent work (Elangovan and Jog, 2024) has shown that even in the special case ε=0, the (0,δ)-LDP privacy polytope exhibits fundamentally different behaviour. In this work, we provide complete characterizations of the extreme points for the low-input-alphabet regime k=2 and k=3 and with arbitrary output alphabet size m. We also identify new extreme mechanisms for larger input alphabet sizes k, of the star configuration type, as introduced by Elangovan and Jog (2024).
Related
- Extreme values of central L-derivatives and heights of Heegner points
- Sofic systems and extreme points of self-affine limit sets
- Extreme points of the unit balls and isometries of noncommutative quasi-Banach Marcinkiewicz spaces
- Geometric Aspects of C*-Extreme Points II
- Hausdorff Dimension of the Set of Extreme Points of a Random Countable Stable Zonotope
BibTeX
@misc{rawat2026extreme,
title = {{Extreme Points of the $(0,δ)$-LDP Polytope with Small Input Size and Arbitrary Output Sizes}},
author = {Supriya Rawat and Myna Vajha and Gowtham R. Kurri and Anand Sarwate},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.09161},
eprint = {2606.09161},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.09161},
}
RIS
TY - UNPB
TI - Extreme Points of the (0,δ)-LDP Polytope with Small Input Size and Arbitrary Output Sizes
AU - Supriya Rawat
AU - Myna Vajha
AU - Gowtham R. Kurri
AU - Anand Sarwate
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2606.09161
UR - https://arxiv.org/abs/2606.09161
AB - The structure of locally differentially private (LDP) mechanisms can be understood through the geometry of the corresponding privacy polytope. While the extreme points of the (ε,0)-LDP polytope are well characterized (Kairouz {et al.}, 2014; Holohan {et al.}, 2017), comparatively little is known for the (ε,δ)-LDP polytope with δ>0. Recent work (Elangovan and Jog, 2024) has shown that even in the special case ε=0, the (0,δ)-LDP privacy polytope exhibits fundamentally different behaviour. In this work, we provide complete characterizations of the extreme points for the low-input-alphabet regime k=2 and k=3 and with arbitrary output alphabet size m. We also identify new extreme mechanisms for larger input alphabet sizes k, of the star configuration type, as introduced by Elangovan and Jog (2024).
ER -