New upper and lower bounds on approximate counting

We show matching upper and lower bounds for approximate counting, as first studied by Morris in the 1970s. We also address the amortized space complexity of the problem, whereby the algorithm must maintain an array of approximate counters while minimizing total memory.

Based on two joint works, with subsets of Ishaq Aden-Ali, Yanjun Han, and Huacheng Yu.