Fetching the paper…
Reading the bibliography…
Motivated by real-life deployments of multi-round federated analytics with secure aggregation, we investigate the fundamental communication-accuracy tradeoffs of the heavy hitter discovery and approximate (open-domain) histogram problems under a linear sketching constraint.
An information statistics approach to data stream and communication complexity
Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, and D. Sivakumar · 2002
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton · 2002
Earlier work this paper cites.
An improved data stream summary: the count-min sketch and its applications
Graham Cormode and S. Muthukrishnan · 2003
Earlier work this paper cites.
Learn more, sample less: control of volume and variance in network measurement
N. Duffield, C. Lund, and M. Thorup · 2005
Earlier work this paper cites.
Learn more, sample less: control of volume and variance in network measurement
N. Duffield, C. Lund, and M. Thorup · 2005
Earlier work this paper cites.
Cores in random hypergraphs and boolean formulas
Michael Molloy · 2005
Earlier work this paper cites.
Combinatorial algorithms for compressed sensing
Graham Cormode and S Muthukrishnan · 2006
Earlier work this paper cites.
Compressed sensing
David L Donoho · 2006
Earlier work this paper cites.
Hellinger strikes back: A note on the multi-party information complexity of and
T. S. Jayram · 2009
Earlier work this paper cites.
Approximate sparse recovery: optimizing time and measurements
Anna C Gilbert, Yi Li, Ely Porat, and Martin J Strauss · 2010
Cited alongside, same era.
Invertible bloom lookup tables
Michael T. Goodrich and Michael Mitzenmacher · 2011
Cited alongside, same era.
Improved concentration bounds for count-sketch
Gregory T Minton and Eric Price · 2014
Cited alongside, same era.
Communication lower bounds for statistical estimation problems via a distributed data processing inequality
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff · 2016
Cited alongside, same era.
Efficient private statistics with succinct sketches
Luca Melis, George Danezis, and Emiliano De Cristofaro · 2016
Cited alongside, same era.
Practical secure aggregation for privacy-preserving machine learning
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth · 2017
Unified lower bounds for interactive high-dimensional estimation under information constraints
Jayadev Acharya, Clément L Canonne, Ziteng Sun, and Himanshu Tyagi · 2020
Later among the works it cites.
Secure single-server aggregation with (poly)logarithmic overhead
James Henry Bell, Kallista A. Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova · 2020
Later among the works it cites.
Privacy-preserving firefox telemetry with prio
Henry Corrigan-Gibbs, Dan Boneh, Gary Chen, Steven Englehardt, Robert Helmer, Chris Hutten-Czapski, Anthony Miyaguchi, Eric Rescorla, and Peter Saint-Andre · 2020
Later among the works it cites.
Lightweight techniques for private heavy hitters
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai · 2021
Later among the works it cites.
Geometric lower bounds for distributed parameter estimation under communication constraints
Yanjun Han, Ayfer Özgür, and Tsachy Weissman · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Prio: Private, robust, and scalable computation of aggregate statistics
Henry Corrigan-Gibbs and Dan Boneh · 2017
Cited alongside, same era.
Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis
Michael Mitzenmacher and Eli Upfal · 2017
Cited alongside, same era.
Towards federated learning at scale: System design
Kallista A. Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander · 2019
Cited alongside, same era.
How to make private distributed cardinality estimation practical, and get differential privacy for free
Changhui Hu, Jin Li, Zheli Liu, Xiaojie Guo, Yu Wei, Xuan Guang, Grigorios Loukides, and Changyu Dong · 2021
Later among the works it cites.
The communication cost of security and privacy in federated frequency estimation, 2022
Wei-Ning Chen, Ayfer Özgür, Graham Cormode, and Akash Bharadwaj · 2022
Later among the works it cites.
Private federated frequency estimation: Adapting to the hardness of the instance, 2023
Jingfeng Wu, Wennan Zhu, Peter Kairouz, and Vladimir Braverman · 2023
Closest in time.