On Low-Risk Heavy Hitters and Sparse Recovery Schemes

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.19OpenAlexW2964227828MaRDI QIDQ5009511

Yi Li, Vasileios Nakos, David P. Woodruff

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1709.02919

zbMATH Keywords

lower boundssparse recoveryheavy hittersspike covariance modelturnstile model

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Finding frequent items in data streams
• Approximate Sparse Recovery: Optimizing Time and Measurements
• Restricted Isometry Property for General p-Norms
• On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Algorithms for dynamic geometric problems over data streams
• Coresets in dynamic geometric data streams
• Data Stream Algorithms via Expander Graphs
• CR-precis: A Deterministic Summary Structure for Update Data Streams
• An improved data stream summary: the count-min sketch and its applications
• Improved Algorithms for Adaptive Compressed Sensing
• ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk
• Compressive sensing with local geometric features
• On the Power of Adaptivity in Sparse Recovery
• (1 + eps)-Approximate Sparse Recovery
• Values of Mills' Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the Argument

This page was built for publication: On Low-Risk Heavy Hitters and Sparse Recovery Schemes