Privately Counting Partially Ordered Data
<|reference_start|>Privately Counting Partially Ordered Data: We consider differentially private counting when each data point consists of $d$ bits satisfying a partial order. Our main technical contribution is a problem-specific $K$-norm mechanism that runs in time $O(d^2)$. Experiments show that, depending on the partial order in question, our solution dominates existing pure differentially private mechanisms, and can reduce their error by an order of magnitude or more.<|reference_end|>
@article{joseph2024privately,
    title={Privately Counting Partially Ordered Data},
    author={Matthew Joseph and M'onica Ribero and Alexander Yu},
    journal={arXiv preprint arXiv:2410.06881},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06881},
    primaryClass={cs.CR}
}