Fetching the paper…
Reading the bibliography…
We develop a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner.
Property testing and its connection to learning and approximation
Oded Goldreich, Shafi Goldwasser, and Dana Ron · 1998
Earlier work this paper cites.
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, and Mario Szegedy · 1999
Earlier work this paper cites.
Property testers for dense constraint satisfaction programs on finite domains
Gunnar Andersson and Lars Engebretsen · 2002
Earlier work this paper cites.
Models and issues in data stream systems
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom · 2002
Earlier work this paper cites.
Random sampling and approximation of max-csps
Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, and Marek Karpinski · 2003
Earlier work this paper cites.
On estimating the average degree of a graph
Oded Goldreich and Dana Ron · 2004
Earlier work this paper cites.
What’s new: finding significant differences in network data streams
Graham Cormode and S. Muthukrishnan · 2005
Earlier work this paper cites.
Approximating the minimum spanning tree weight in sublinear time
Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan · 2005
Earlier work this paper cites.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith · 2006
Earlier work this paper cites.
Differential privacy
Cynthia Dwork · 2006
Earlier work this paper cites.
Tolerant property testing and distance approximation
Michal Parnas, Dana Ron, and Ronitt Rubinfeld · 2006
Earlier work this paper cites.
Smooth histograms for sliding windows
Vladimir Braverman and Rafail Ostrovsky · 2007
Earlier work this paper cites.
The sliding-window computation model and results
Mayur Datar and Rajeev Motwani · 2007
Earlier work this paper cites.
Testing versus estimation of graph properties
Eldar Fischer and Ilan Newman · 2007
Earlier work this paper cites.
Smooth sensitivity and sampling in private data analysis
Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith · 2007
Earlier work this paper cites.
The communication and streaming complexity of computing the longest common and increasing subsequences
Xiaoming Sun and David P. Woodruff · 2007
Earlier work this paper cites.
Streaming in a connected world: querying and tracking distributed data streams
Graham Cormode and Minos N. Garofalakis · 2008
Earlier work this paper cites.
A combinatorial characterization of the testable graph properties: It’s all about regularity
Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira · 2009
Earlier work this paper cites.
Differential privacy and robust statistics
Cynthia Dwork and Jing Lei · 2009
Earlier work this paper cites.
Effective computations on sliding windows
Vladimir Braverman and Rafail Ostrovsky · 2010
Cited alongside, same era.
Differentially private combinatorial optimization
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar · 2010
Cited alongside, same era.
On the geometry of differential privacy
Moritz Hardt and Kunal Talwar · 2010
Cited alongside, same era.
An optimal algorithm for the distinct elements problem
Daniel M. Kane, Jelani Nelson, and David P. Woodruff · 2010
Cited alongside, same era.
Fast moment estimation in data streams in optimal space
Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff · 2011
Cited alongside, same era.
Pan-private algorithms via statistics on sketches
Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright · 2011
Cited alongside, same era.
Fingerprinting codes and the price of approximate differential privacy
Mark Bun, Jonathan R. Ullman, and Salil P. Vadhan · 2018
Later among the works it cites.
High probability frequency moment sketches
Sumit Ganguly and David P. Woodruff · 2018
Later among the works it cites.
Near optimal linear algebra in the online and sliding window models
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou · 2020
Later among the works it cites.
Optimal streaming and tracking distinct elements with high probability
Jaroslaw Blasiok · 2020
Later among the works it cites.
A survey on differentially private machine learning [review article]
Maoguo Gong, Yu Xie, Ke Pan, Kaiyuan Feng, and Alex Kai Qin · 2020
Later among the works it cites.
The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Analyzing graph structure via linear measurements
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2012
Cited alongside, same era.
The johnson-lindenstrauss transform itself preserves differential privacy
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet · 2012
Cited alongside, same era.
Optimal sampling from sliding windows
Vladimir Braverman, Rafail Ostrovsky, and Carlo Zaniolo · 2012
Cited alongside, same era.
Approximate frequency counts over data streams
Gurmeet Singh Manku and Rajeev Motwani · 2012
Cited alongside, same era.
Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito · 2012
Cited alongside, same era.
Estimating the number of connected components in sublinear time
Petra Berenbrink, Bruce Krayenhoff, and Frederik Mallmann-Trenn · 2014
Cited alongside, same era.
Adam D. Smith, Shuang Song, and Abhradeep Thakurta · 2020
Later among the works it cites.
Fast and memory efficient differentially private-sgd via JL projections
Zhiqi Bu, Sivakanth Gopi, Janardhan Kulkarni, Yin Tat Lee, Judy Hanwen Shen, and Uthaipon Tantipongpipat · 2021
Later among the works it cites.
Symmetric norm estimation and regression on sliding windows
Vladimir Braverman, Viska Wei, and Samson Zhou · 2021
Later among the works it cites.
On efficient distance approximation for graph properties
Nimrod Fiat and Dana Ron · 2021
Later among the works it cites.
Robust and private learning of halfspaces
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Thao Nguyen · 2021
Later among the works it cites.
Tight bounds for adversarially robust streams and sliding windows via difference estimators
David P. Woodruff and Samson Zhou · 2021
Later among the works it cites.
Privately estimating graph parameters in sublinear time
Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee · 2022
Closest in time.
Private data stream analysis for universal symmetric norm estimation
Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, and Samson Zhou · 2022
Closest in time.
Improved sliding window algorithms for clustering and coverage via bucketing-based sketches
Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, and Peilin Zhong · 2022
Closest in time.
Tolerant bipartiteness testing in dense graphs
Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen · 2022
Closest in time.
Truly perfect samplers for data streams and sliding windows
Rajesh Jayaram, David P. Woodruff, and Samson Zhou · 2022
Closest in time.
Additive noise mechanisms for making randomized approximation algorithms differentially private
Jakub Tetek · 2022
Closest in time.
Differentially private fractional frequency moments estimation with polylogarithmic space
Lun Wang, Iosif Pinelis, and Dawn Song · 2022
Closest in time.
Differentially private continual releases of streaming frequency moment estimations
Alessandro Epasto, Jieming Mao, Andres Muñoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong · 2023
Closest in time.