Differential Privacy And The Complexity Of Simple Queries
summary
Shows an explicit information–computation gap: answering k arbitrary bounded mean queries privately needs about √k samples with any polynomial-time algorithm, while exponential-time algorithms get down to about √d samples (d is data dimension). Practical methods are the Gaussian mechanism (noise ∼√k/n → sample need ≈d^{m/2} for m‑way marginals) and the projection + SDP relaxation approach (gives roughly d^{m/4} in best efficient results); a tensor‑completion barrier and refutation reductions give D^{3/4}-style lower bounds for M=3.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 3:16Data privacy fundamentals
- 6:54Privacy attacks and mechanisms
- 9:22Differential privacy definition
- 13:50Answering statistical queries
- 21:10Computational complexity trade-offs
- 25:46Marginal query problems
- 30:45Approaches and barriers
- 37:51The projection mechanism
- 43:25Open challenges and discussion
related talks
26mAlgorithms with More Granular Differential Privacy Guarantees
01h 03mStatistical Inference and Privacy, Part II
01h 14mStatistical Inference and Privacy, Part III
01h 00mDifferential Privacy: Fundamentals to Forefront I
01h 03mSimons Institute Live Stream
01h 02mLarge-Scale Private Learning, Part I
43mDifferential Privacy Meets Robust Statistics
01h 14mTutorial: Privacy, Part II