# Permute-and-Flip: A new mechanism for differentially private selection

arXiv: https://arxiv.org/abs/2010.12603 · HTML: https://mlsanity.com/paper/2010.12603/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2020.

## Built on by (most cited first, 22 of 22)

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation](https://mlsanity.com/paper/2309.11765/) (2023)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [On Privacy and Personalization in Cross-Silo Federated Learning](https://mlsanity.com/paper/2206.07902/) (2022)
- [Permute-and-Flip: An optimally stable and watermarkable decoder for LLMs](https://mlsanity.com/paper/2402.05864/) (2024)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [On the Privacy of Selection Mechanisms with Gaussian Noise](https://mlsanity.com/paper/2402.06137/) (2024)
- [Differentially Private Top-k Selection via Canonical Lipschitz Mechanism](https://mlsanity.com/paper/2201.13376/) (2022)
- [Differentially-Private Decision Trees and Provable Robustness to Data Poisoning](https://mlsanity.com/paper/2305.15394/) (2023)
- [Randomized algorithms for precise measurement of differentially-private, personalized recommendations](https://mlsanity.com/paper/2308.03735/) (2023)
- [Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise](https://mlsanity.com/paper/2407.20068/) (2024)
- [Faster Private Minimum Spanning Trees](https://mlsanity.com/paper/2408.06997/) (2024)
- [Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy](https://mlsanity.com/paper/2502.10997/) (2025)
- [Differentially Private Conditional Independence Testing](https://mlsanity.com/paper/2306.06721/) (2023)
- [Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation](https://mlsanity.com/paper/2412.10130/) (2024)
- [Private Selection with Heterogeneous Sensitivities](https://mlsanity.com/paper/2501.05309/) (2025)
- [Training Set Reconstruction from Differentially Private Forests: How Effective is DP?](https://mlsanity.com/paper/2502.05307/) (2025)
- [Differentially Private Selection using Smooth Sensitivity](https://mlsanity.com/paper/2504.08086/) (2025)
- [DPrivBench: Benchmarking LLMs' Reasoning for Differential Privacy](https://mlsanity.com/paper/2604.15851/) (2026)
- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)
- [Plausible Deniability Guarantees for Whistleblowers](https://mlsanity.com/paper/2607.13928/) (2026)
- [ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignment](https://mlsanity.com/paper/2609.21899/) (2026)

## Abstract (arXiv)

We consider the problem of differentially private selection. Given a finite set of candidate items and a quality score for each item, our goal is to design a differentially private mechanism that returns an item with a score that is as high as possible. The most commonly used mechanism for this task is the exponential mechanism. In this work, we propose a new mechanism for this task based on a careful analysis of the privacy constraints. The expected score of our mechanism is always at least as large as the exponential mechanism, and can offer improvements up to a factor of two. Our mechanism is simple to implement and runs in linear time.