Finding Heavy Hitters from Lossy or Noisy Data

DOI10.1007/978-3-642-40328-6_25zbMath1405.68276MaRDI QIDQ2851870

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

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

zbMATH Keywords

enumeration of heavy hitters; learning discrete distributions; population recovery

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T05: Learning and adaptive systems in artificial intelligence

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Population recovery and partial identification