Finding heavy hitters from lossy or noisy data

DOI10.1007/978-3-642-40328-6_25zbMATH Open1405.68276OpenAlexW2168561001MaRDI QIDQ2851870FDOQ2851870

Authors: Lucia Batman, Russell Impagliazzo, Cody D. Murray, Ramamohan Paturi 

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40328-6_25

Recommendations

• An optimal algorithm for \(\ell_1\)-heavy hitters in insertion streams and related problems
• Distributed private heavy hitters
• New algorithms for heavy hitters in data streams (invited talk)
• On low-risk heavy hitters and sparse recovery schemes
• Deterministic heavy hitters with sublinear query time

zbMATH Keywords

enumeration of heavy hitterslearning discrete distributionspopulation recovery

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (1)

• Population recovery and partial identification

This page was built for publication: Finding heavy hitters from lossy or noisy data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851870)