mlsanityData to 14 Oct 2026

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

arXiv 2010.12603 ↗First posted 23 Oct 2020cs.CRcited by 22

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 2; 2023: 6; 2024: 5; 2025: 4; 2026: 4.

22 papers.

Sort:

By area:

  1. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 153
  2. 2023Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generationcited by 96
  3. 2021Leveraging Public Data for Practical Private Query Releasecited by 39
  4. 2022On Privacy and Personalization in Cross-Silo Federated Learningcited by 36
  5. 2024Permute-and-Flip: An optimally stable and watermarkable decoder for LLMscited by 22
  6. 2023Unbounded Differentially Private Quantile and Maximum Estimationcited by 6
  7. 2024On the Privacy of Selection Mechanisms with Gaussian Noisecited by 3
  8. 2022Differentially Private Top-k Selection via Canonical Lipschitz Mechanismcited by 2
  9. 2023Differentially-Private Decision Trees and Provable Robustness to Data Poisoningcited by 1
  10. 2023Randomized algorithms for precise measurement of differentially-private, personalized recommendationscited by 1
  11. 2024Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noisecited by 1
  12. 2024Faster Private Minimum Spanning Treescited by 1
10 more
  1. 2025Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacycited by 1
  2. 2023Differentially Private Conditional Independence Testingcited by 0
  3. 2024Optimal Bounds for Private Minimum Spanning Trees via Input Perturbationcited by 0
  4. 2025Private Selection with Heterogeneous Sensitivitiescited by 0
  5. 2025Training Set Reconstruction from Differentially Private Forests: How Effective is DP?cited by 0
  6. 2025Differentially Private Selection using Smooth Sensitivitycited by 0
  7. 2026DPrivBench: Benchmarking LLMs' Reasoning for Differential Privacycited by 0
  8. 2026Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Treescited by 0
  9. 2026Plausible Deniability Guarantees for Whistleblowerscited by 0
  10. 2026ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignmentcited by 0