On low-risk heavy hitters and sparse recovery schemes

• Main Authors: Li, Yi, Nakos, Vasileios, Woodruff, David P.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2018
• Subjects: Heavy Hitters; DRNTU::Science::Mathematics; Sparse Recovery
• Online Access: https://hdl.handle.net/10356/89386; http://hdl.handle.net/10220/46212
• Institution: Nanyang Technological University

We study the heavy hitters and related sparse recovery problems in the low failure probability regime. This regime is not well-understood, and the main previous work on this is by Gilbert et al. (ICALP'13). We recognize an error in their analysis, improve their results, and contribute new spars...