Fetching the paper…
Reading the bibliography…
This paper proves that an "old dog", namely -- the classical Johnson-Lindenstrauss transform, "performs new tricks" -- it gives a novel way of preserving differential privacy.
Multidimensional Gaussian distributions
K.S. Miller · 1964
Earlier work this paper cites.
Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
Stanley L. Warner · 1965
Earlier work this paper cites.
Extensions of Lipschitz maps into a Hilbert space
W. Johnson and J. Lindenstauss · 1984
Earlier work this paper cites.
On lipschitz embedding of finite metric spaces in hilbert space
J Bourgain · 1985
Earlier work this paper cites.
Matrix Analysis
Roger A. Horn and Charles R. Johnson · 1990
Earlier work this paper cites.
The geometry of graphs and some of its algorithmic applications
N. Linial, E. London, and Y. Rabinovich · 1994
Earlier work this paper cites.
Approximating s-t minimum cuts in o ~ ( n 2 ) \tilde{o}(n^{2}) time
András A. Benczúr and David R. Karger · 1996
Earlier work this paper cites.
Two algorithms for nearest-neighbor search in high dimensions
Jon M. Kleinberg · 1997
Earlier work this paper cites.
Approximate nearest neighbors: Towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
Latent semantic indexing: A probabilistic analysis
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, S. Vempala, and Santosh Vempala · 1998
Earlier work this paper cites.
Clustering for edge-cost minimization (extended abstract)
Leonard J. Schulman · 2000
Earlier work this paper cites.
Revealing information while preserving privacy
Irit Dinur and Kobbi Nissim · 2003
Earlier work this paper cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 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.
Toward privacy in public databases
Shuchi Chawla, Cynthia Dwork, Frank Mcsherry, Adam Smith, and Larry Joseph Stockmeyer · 2005
Cited alongside, same era.
The Random Projection Method
S.S. Vempala · 2005
Cited alongside, same era.
Approximate nearest neighbors and the fast johnson-lindenstrauss transform
Nir Ailon and Bernard Chazelle · 2006
Cited alongside, same era.
Kernels as features: On kernels, margins, and low-dimensional mappings
Maria-Florina Balcan, Avrim Blum, and Santosh Vempala · 2006
Cited alongside, same era.
Our data, ourselves: Privacy via distributed noise generation
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor · 2006
Cited alongside, same era.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, and Adam Smith · 2006
Cited alongside, same era.
Accurate estimation of the degree distribution of private networks
Michael Hay, Chao Li, Gerome Miklau, and David Jensen · 2009
Later among the works it cites.
Differentially private recommender systems: Building privacy into the netflix prize contenders
Frank McSherry and Ilya Mironov · 2009
Later among the works it cites.
A sparse johnson: Lindenstrauss transform
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlos · 2010
Later among the works it cites.
Boosting and differential privacy
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan · 2010
Later among the works it cites.
Differential privacy for statistics: What we know and what we want to learn
Cynthia Dwork and Adam Smith · 2010
Later among the works it cites.
A simple and practical algorithm for differentially private data release
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Cited alongside, same era.
Perturbation Bounds for Matrix Eigenvalues (Classics in Applied Mathematics)
R. Bhatia · 2007
Cited alongside, same era.
Mechanism design via differential privacy
Frank McSherry and Kunal Talwar · 2007
Cited alongside, same era.
Smooth sensitivity and sampling in private data analysis
K. Nissim, S. Raskhodnikova, and A. Smith · 2007
Cited alongside, same era.
A simple proof of the restricted isometry property for random matrices
Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin · 2008
Cited alongside, same era.
A learning theory approach to non-interactive database privacy
A. Blum, K. Ligett, and A. Roth · 2008
Cited alongside, same era.
Moritz Hardt, Katrina Ligett, and Frank McSherry · 2010
Later among the works it cites.
A multiplicative weights mechanism for privacy-preserving data analysis
M. Hardt and G.N. Rothblum · 2010
Later among the works it cites.
Interactive privacy via the median mechanism
A. Roth and T. Roughgarden · 2010
Later among the works it cites.
A firm foundation for private data analysis
Cynthia Dwork · 2011
Later among the works it cites.
Privately releasing conjunctions and the statistical query barrier
Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman · 2011
Later among the works it cites.
Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp · 2011
Later among the works it cites.
Private analysis of graph structure
Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev · 2011
Later among the works it cites.
Iterative constructions and private data release
Anupam Gupta, Aaron Roth, and Jonathan Ullman · 2012
Closest in time.
Beating randomized response on incoherent matrices
Moritz Hardt and Aaron Roth · 2012
Closest in time.