# Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes arXiv: https://arxiv.org/abs/2307.07604 ยท HTML: https://mlsanity.com/paper/2307.07604/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 24 of its 50 references that are in the map. - First posted on arXiv 14 Jul 2023. ## Builds on (most cited first, 24 of 24) - [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017) - [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018) - [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013) - [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015) - [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021) - [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014) - [Preventing False Discovery in Interactive Data Analysis is Hard](https://mlsanity.com/paper/1408.1655/) (2014) - [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017) - [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020) - [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (2021) - [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021) - [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021) - [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022) - [Private Query Release Assisted by Public Data](https://mlsanity.com/paper/2004.10941/) (2020) - [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016) - [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021) - [Differentially Private k-Means with Constant Multiplicative Error](https://mlsanity.com/paper/1804.08001/) (2018) - [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023) - [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016) - [Clustering Algorithms for the Centralized and Local Models](https://mlsanity.com/paper/1707.04766/) (2017) - [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021) - [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021) - [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023) - [Differentially Private Sampling from Distributions](https://mlsanity.com/paper/2211.08193/) (2022) ## Built on by (most cited first, 8 of 8) - [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023) - [Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes](https://mlsanity.com/paper/2404.17714/) (2024) - [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024) - [On Differentially Private Subspace Estimation in a Distribution-Free Setting](https://mlsanity.com/paper/2402.06465/) (2024) - [Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy](https://mlsanity.com/paper/2603.19703/) (2026) - [Bayesian Perspective on Memorization and Reconstruction](https://mlsanity.com/paper/2505.23658/) (2025) - [Lower Bounds for Public-Private Learning under Distribution Shift](https://mlsanity.com/paper/2507.17895/) (2025) - [A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning](https://mlsanity.com/paper/2605.19813/) (2026) ## Abstract (arXiv) Fingerprinting arguments, first introduced by Bun, Ullman, and Vadhan (STOC 2014), are the most widely used method for establishing lower bounds on the sample complexity or error of approximately differentially private (DP) algorithms. Still, there are many problems in differential privacy for which we don't know suitable lower bounds, and even for problems that we do, the lower bounds are not smooth, and usually become vacuous when the error is larger than some threshold. We present a new framework and tools to generate smooth lower bounds on the sample complexity of differentially private algorithms satisfying very weak accuracy. We illustrate the applicability of our method by providing new lower bounds in various settings: 1. A tight lower bound for DP averaging in the low-accuracy regime, which in particular implies a lower bound for the private 1-cluster problem introduced by Nissim, Stemmer, and Vadhan (PODS 2016). 2. A lower bound on the additive error of DP algorithms for approximate k-means clustering and general (k,z)-clustering, as a function of the multiplicative error, which is tight for a constant multiplication error. 3. A lower bound for estimating the top singular vector of a matrix under DP in low-accuracy regimes, which is a special case of DP subspace estimation studied by Singhal and Steinke (NeurIPS 2021). Our main technique is to apply a padding-and-permuting transformation to a fingerprinting code. However, rather than proving our results using a black-box access to an existing fingerprinting code (e.g., Tardos' code), we develop a new fingerprinting lemma that is stronger than those of Dwork et al. (FOCS 2015) and Bun et al. (SODA 2017), and prove our lower bounds directly from the lemma. Our lemma, in particular, gives a simpler fingerprinting code construction with optimal rate (up to polylogarithmic factors) that is of independent interest.