Simons Institute Live Stream
summary
Covers concrete algorithms and bounds for answering counting (linear) queries under differential privacy: the Gaussian noise mechanism adds iid Gaussian scaled to the workload L2 sensitivity (largest column norm of the query matrix), yielding worst‑case error ≈ sensitivity·√k; for one‑way marginals this is optimal. For thresholds a tree/strategy basis cuts error to O(log U). The matrix mechanism factors W = R·A, solves an SDP minimizing max row/column norms, matches optimal error for large databases but can be suboptimal when n is small; reconstruction lower bounds need n ≳ k/ε.
AI-written summary · about
chapters (14)
- 0:00Intro
- 1:38Basics
- 6:27Counting Queries
- 8:54Histogram
- 11:57Query Matrix
- 15:25Error
- 20:38Types of mechanisms
- 24:19Gaussian noise mechanism
- 35:14Factoring
- 41:48Matrix mechanism
- 48:30Sensitivity polytope
- 52:16Semidefinite program
- 55:21Optimal error
- 57:58Small databases
related talks
01h 00mDifferential Privacy And The Complexity Of Simple Queries
26mAaron Roth, Associate Professor, University of Pennsylvania, NYC 2017
54mNode Privacy, High-dimensional Graph Summaries, and Block Models
47mBlack-box Random Differential Privacy with Sensitivity Sampling
01h 14mTutorial: Privacy, Part III
39mVirtual talk by Jonathan Ullman (Northeastern)
01h 00mDifferential Privacy: Fundamentals to Forefront I
26mAlgorithms with More Granular Differential Privacy Guarantees