Consistency with External Knowledge: The TopDown Algorithm
Talkat Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019) · 2019-03-04..03-08·
summary
TopDown builds a differentially private microdata pipeline for the 2020 census that publishes hierarchical histograms over 12 billion cells (about 300M people, ~6M blocks) by iteratively solving national then state then county ... down to blocks, using a high-dimensional matrix mechanism for measurements, L2 solves and LP rounding to enforce nonnegative integer counts, exploiting sparsity and totally unimodular structure. It handles NP‑complete invariant consistency checks (state totals, GQ types, housing units) with flow reductions, cutting planes and a failsafe that relaxes parent consistency.
AI-written summary · about
chapters (12)
- 0:00Start
- 3:07Formal Privacy
- 5:08Requirements
- 7:00Consistency with External Knowledge
- 12:10TopDown Framework (without invariants)
- 13:24National Level Histogram H
- 14:43National Histogram Linear solve
- 21:10Outline
- 22:19An Example (1)
- 26:17Implied Constraints
- 31:21Workarounds
- 33:17Current Invariants
related talks
15mDifferentially Private Algorithms for 2020 Decennial Census Detailed DHC Race & Ethnicity
11mCausal Inference With Corrupted Data: Measurement Error, Missing Values, Discretization, And...
43mTopological data analysis: How to quantify "holes" in your data and why?
34mTopological Data Analysis
50mThe Shape of Data: Machine Learning and Topology
27mThe ethical algorithm
22mCOVID-19: Data Science & Expertise
30mDisambiguating Explicit and Implicit Geographic References...