English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Fingerprinting arguments, first introduced by Bun, Ullman, and Vadhan (STOC2014), are the most widely used method for establishing lower bounds on thesample complexity or error of approximately differentially private (DP)algorithms. Still, there are many problems in differential privacy for which wedon't know suitable lower bounds, and even for problems that we do, the lowerbounds are not smooth, and usually become vacuous when the error is larger thansome threshold.  In this work, we present a simple method to generate hard instances byapplying a padding-and-permuting transformation to a fingerprinting code. Weillustrate the applicability of this method by providing new lower bounds invarious settings:  1. A tight lower bound for DP averaging in the low-accuracy regime, which inparticular implies a new lower bound for the private 1-cluster problemintroduced by Nissim, Stemmer, and Vadhan (PODS 2016).  2. A lower bound on the additive error of DP algorithms for approximatek-means clustering, as a function of the multiplicative error, which is tightfor a constant multiplication error.  3. A lower bound for estimating the top singular vector of a matrix under DPin low-accuracy regimes, which is a special case of DP subspace estimationstudied by Singhal and Steinke (NeurIPS 2021).  Our main technique is to apply a padding-and-permuting transformation to afingerprinting code. However, rather than proving our results using a black-boxaccess to an existing fingerprinting code (e.g., Tardos' code), we develop anew fingerprinting lemma that is stronger than those of Dwork et al. (FOCS2015) and Bun et al. (SODA 2017), and prove our lower bounds directly from thelemma. Our lemma, in particular, gives a simpler fingerprinting codeconstruction with optimal rate (up to polylogarithmic factors) that is ofindependent interest.

Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes