On the amortized complexity of approximate counting

DOI10.4230/LIPICS.APPROX/RANDOM.2024.33MaRDI QIDQ6920809zbMATH OpenFDO

Authors Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, Huacheng Yu

Publication date 6 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.33

zbMATH Keywords

approximate countinginformation complexitylower boundsstreaming

Mathematics Subject Classification ID

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

Cites work

• An information statistics approach to data stream and communication complexity
• Counting large numbers of events in small registers
• Elements of Information Theory
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• The coin problem with applications to data streams

This page was built for publication: On the amortized complexity of approximate counting

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