2019

Pan-Private Uniformity Testing

Amin, Kareem, Joseph, Matthew, Mao, Jieming

Understand

A centrally differentially private algorithm maps raw data to differentially private outputs.

In contrast, a locally differentially private algorithm may only access data through public interaction with data holders, and this interaction must be a differentially private function of the data.
We study the intermediate model of pan-privacy.
Unlike a locally private algorithm, a pan-private algorithm receives data in the clear.

Built on

Domain compression and its application to randomness-optimal distributed goodness-of-fit
Original
Jayadev Acharya, Clément L Canonne, Yanjun Han, Ziteng Sun, and Himanshu Tyagi · 1907
Earlier work this paper cites.
Oblivious data structures: Applications to cryptography
Daniele Micciancio · 1997
Earlier work this paper cites.
On testing expansion in bounded-degree graphs
Oded Goldreich and Dana Ron · 2000
Earlier work this paper cites.
Anti-persistence: History independent data structures
Moni Naor and Vanessa Teague · 2001
Earlier work this paper cites.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006
Earlier work this paper cites.
Strongly history-independent hashing with applications
Guy E. Blelloch and Daniel Golovin · 2007
Earlier work this paper cites.
A coincidence-based test for uniformity given very sparsely sampled discrete data
Liam Paninski · 2008
Earlier work this paper cites.
The limits of two-party differential privacy
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil Vadhan · 2010
Earlier work this paper cites.
Private and continual release of statistics
T.-H. Hubert Chan, Elaine Shi, and Dawn Song · 2011
Earlier work this paper cites.
What can we learn privately?
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith · 2011
Earlier work this paper cites.
Pan-private algorithms via statistics on sketches
Darakhshan Mir, Shan Muthukrishnan, Aleksandar Nikolov, and Rebecca N Wright · 2011
Earlier work this paper cites.
Optimal lower bound for differentially private multi-party aggregation
TH Hubert Chan, Elaine Shi, and Dawn Song · 2012
Earlier work this paper cites.
A competitive test for uniformity of monotone distributions
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Suresh · 2013
Earlier work this paper cites.

Similar

Local privacy and statistical minimax rates
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright · 2013
Cited alongside, same era.
Optimal algorithms for testing closeness of discrete distributions
Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant · 2014
Cited alongside, same era.
The algorithmic foundations of differential privacy
Cynthia Dwork, Aaron Roth, et al · 2014
Cited alongside, same era.
An automatic inequality prover and instance optimal identity testing
Gregory Valiant and Paul Valiant · 2014
Cited alongside, same era.
Optimal testing for properties of distributions
Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath · 2015
Cited alongside, same era.
Local, private, efficient protocols for succinct histograms
Raef Bassily and Adam Smith · 2015
Cited alongside, same era.
A survey on distribution testing: Your data is big. but is it blue?
Clément L Canonne · 2015
Cited alongside, same era.
A short note on poisson tail bounds
Clément L Canonne · 2016
Cited alongside, same era.
Learning with privacy at scale
Differential Privacy Team Apple · 2017
Cited alongside, same era.
Prochlo: Strong privacy for analytics in the crowd
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld · 2017
Cited alongside, same era.
Priv’it: private and sample efficient identity testing
Bryan Cai, Constantinos Daskalakis, and Gautam Kamath · 2017
Cited alongside, same era.
Collecting telemetry data privately
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin · 2017
Cited alongside, same era.

Then

Differentially private testing of identity and closeness of discrete distributions
Jayadev Acharya, Ziteng Sun, and Huanyu Zhang · 2018
Later among the works it cites.
Differentially private identity and equivalence testing of discrete distributions
Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld · 2018
Later among the works it cites.
Heavy hitters and the structure of local privacy
Mark Bun, Jelani Nelson, and Uri Stemmer · 2018
Later among the works it cites.
Usable differential privacy: A case study with psi
Original
Jack Murtagh, Kathryn Taylor, George Kellaris, and Salil Vadhan · 2018
Later among the works it cites.
Distributed differential privacy via shuffling
Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev · 2019
Closest in time.
Communication and memory efficient testing of discrete distributions
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, and Sankeerth Rao · 2019
Closest in time.
Lower bounds for locally private estimation via communication complexity
John Duchi and Ryan Rogers · 2019
Closest in time.
Enabling developers and organizations to use differential privacy
Miguel Guevara · 2019
Closest in time.
The role of interactivity in local differential privacy
Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth · 2019
Closest in time.
Facebook privacy-protected urls light table release
Solomon Messing, Christina DeGregorio, Bennett Hillenbrand, Gary King, Saurav Mahanti, Chaya Nayak, Nathaniel Persily, Bogdan State, and Arjun Wilkins · 2019
Closest in time.
Disclosure avoidance for block level data and protection of confidentiality in public tabulations
John Abowd · 2020
Closest in time.
Exponential separations in local differential privacy
Matthew Joseph, Jieming Mao, and Aaron Roth · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…