Fetching the paper…
Reading the bibliography…
We show new lower bounds on the sample complexity of $(\varepsilon, \delta)$-differentially private algorithms that accurately answer large sets of counting queries.
Collusion-secure fingerprinting for digital data
Dan Boneh and James Shaw · 1998
Earlier work this paper cites.
Concentration of measure for randomized algorithms: techniques and applications
Devdatt P. Dubhashi and Sandeep Sen · 2001
Earlier work this paper cites.
Revealing information while preserving privacy
Irit Dinur and Kobbi Nissim · 2003
Earlier work this paper cites.
Privacy-preserving datamining on vertically partitioned databases
Cynthia Dwork and Kobbi Nissim · 2004
Earlier work this paper cites.
Practical privacy: the SuLQ framework
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim · 2005
Earlier work this paper cites.
Our data, ourselves: Privacy via distributed noise generation
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor · 2006
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.
Privacy, accuracy, and consistency too: a holistic solution to contingency table release
Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar · 2007
Earlier work this paper cites.
The price of privacy and the limits of lp decoding
Cynthia Dwork, Frank McSherry, and Kunal Talwar · 2007
Earlier work this paper cites.
A learning theory approach to non-interactive database privacy
Avrim Blum, Katrina Ligett, and Aaron Roth · 2008
Earlier work this paper cites.
Traitor tracing with constant size ciphertext
Dan Boneh and Moni Naor · 2008
Earlier work this paper cites.
New efficient attacks on statistical disclosure control mechanisms
Cynthia Dwork and Sergey Yekhanin · 2008
Earlier work this paper cites.
Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays
Nils Homer, Szabolcs Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John V Pearson, Dietrich A Stephan, Stanley F Nelson, and David W Craig · 2008
Earlier work this paper cites.
Optimal probabilistic fingerprint codes
Gábor Tardos · 2008
Earlier work this paper cites.
Neural Network Learning: Theoretical Foundations
Martin Anthony and Peter L. Bartlett · 2009
Earlier work this paper cites.
On the complexity of differentially private data release: efficient algorithms and hardness results
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan · 2009
Earlier work this paper cites.
Genomic privacy and limits of individual detection in a pool
Sriram Sankararaman, Guillaume Obozinski, Michael I Jordan, and Eran Halperin · 2009
Earlier work this paper cites.
Robust fingerprinting codes: a near optimal construction
Dan Boneh, Aggelos Kiayias, and Hart William Montgomery · 2010
Earlier work this paper cites.
Bounds on the sample complexity for private learning and private data release
Amos Beimel, Shiva Prasad Kasiviswanathan, and Kobbi Nissim · 2010
Cited alongside, same era.
Boosting and differential privacy
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan · 2010
Cited alongside, same era.
A multiplicative weights mechanism for privacy-preserving data analysis
Moritz Hardt and Guy N. Rothblum · 2010
Cited alongside, same era.
On the geometry of differential privacy
Moritz Hardt and Kunal Talwar · 2010
Cited alongside, same era.
The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman · 2010
Cited alongside, same era.
Differential privacy and the fat-shattering dimension of linear queries
Aaron Roth · 2010
Private learning and sanitization: Pure vs. approximate differential privacy
Amos Beimel, Kobbi Nissim, and Uri Stemmer · 2013
Closest in time.
Local privacy and statistical minimax rates
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright · 2013
Closest in time.
Efficient algorithms for privately releasing marginals via convex programming
Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar · 2013
Closest in time.
The geometry of differential privacy: the sparse and approximate cases
Aleksandar Nikolov, Kunal Talwar, and Li Zhang · 2013
Closest in time.
Answering n 2 + o ( 1 ) n^{2+o(1)} counting queries with differential privacy is hard
Jonathan Ullman · 2013
Closest in time.
Private empirical risk minimization: Efficient algorithms and tight error bounds
Raef Bassily, Adam Smith, and Abhradeep Thakurta · 2014
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Interactive privacy via the median mechanism
Aaron Roth and Tim Roughgarden · 2010
Cited alongside, same era.
Privately releasing conjunctions and the statistical query barrier
Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman · 2011
Cited alongside, same era.
A Study in Privacy and Fairness in Sensitive Data Analysis
Moritz Hardt · 2011
Cited alongside, same era.
What can we learn privately?
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith · 2011
Cited alongside, same era.
PCPs and the hardness of generating private synthetic data
Jonathan Ullman and Salil P. Vadhan · 2011
Cited alongside, same era.
Lower bounds in differential privacy
Anindya De · 2012
Cited alongside, same era.
Closest in time.
Faster private release of marginals on small databases
Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, and Andrew Wan · 2014
Closest in time.
Analyze gauss: optimal bounds for privacy-preserving principal component analysis
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang · 2014
Closest in time.
Preventing false discovery in interactive data analysis is hard
Moritz Hardt and Jonathan Ullman · 2014
Closest in time.
Space lower bounds for itemset frequency sketches
Edo Liberty, Michael Mitzenmacher, Justin Thaler, and Jonathan Ullman · 2014
Closest in time.
Differentially private release and learning of threshold functions
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan · 2015
Closest in time.
More general queries and less generalization error in adaptive data analysis
Raef Bassily, Adam Smith, Thomas Steinke, and Jonathan Ullman · 2015
Closest in time.
Preserving statistical validity in adaptive data analysis
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth · 2015
Closest in time.
Robust traceability from trace amounts
Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan · 2015
Closest in time.
Between pure and approximate differential privacy
Thomas Steinke and Jonathan Ullman · 2015
Closest in time.
Preventing false discovery in interactive data analysis is hard
Thomas Steinke and Jonathan Ullman · 2015
Closest in time.
The complexity of differential privacy, 2016
Salil Vadhan · 2016
Closest in time.