networks
The graph that knew your name
It is 2008, and a social-media company has released an "anonymized" friendship graph for research — names stripped, identifiers randomized, structure intact. The structure is the identifier: degrees, neighborhoods, and subgraph patterns are as distinctive as fingerprints, and an attacker who knows a handful of a target's friendships — or controls a few accounts planted before release — can locate the target in the anonymous graph and unmask their whole neighborhood. Demonstrate the re-identification rigorously, quantify how little auxiliary knowledge suffices, and then face the constructive question: what graph statistics can be released with formal privacy guarantees, and what utility survives. Get it wrong and every "anonymized" network release — social, medical, financial — is a deanonymization dataset waiting for its adversary.
Who this problem belongs to
The two figures whose methods fit it best, out of 48 in contention.
This is Dwork's own work, not an analogy. With Backstrom and Kleinberg, her 2007 paper 'Wherefore Art Thou R3579X?' rigorously demonstrated that a small number of planted or known relationships suffice to re-identify targets in an anonymized social graph, formalizing both active attacks (planting fake accounts before release) and passive attacks (using existing auxiliary knowledge). Her subsequent, foundational development of differential privacy directly answers the problem's constructive half: what can be released about a graph's structure with a formal, provable privacy guarantee, and what utility survives that guarantee. She is not applying an analogous toolkit; she built the specific mathematics of both the attack and the principled defense this problem describes, in exactly this era, on exactly this question.
Kleinberg co-authored the same 2007 paper with Backstrom and Dwork that rigorously demonstrated social-graph re-identification from a handful of planted or known auxiliary relationships, making this problem essentially a restatement of his own published result. His deep, career-long fluency with network structure, degree distributions, and small-world navigability gives him the precise technical vocabulary for explaining why structure alone is as distinctive as a fingerprint. He also brings the algorithmic-fairness lens needed for the problem's second half, weighing what utility a privacy-preserving release can still offer. The only reason he is not scored above Dwork is that the differential-privacy formalism answering the constructive question was principally her contribution, with Kleinberg as network-structure co-architect of the attack.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
48 figures are scored on this problem. Draw it in a battle to see where you land.