New upper and lower bounds on approximate counting

on YouTube ↗48m

" summary

Proves tight upper and lower bounds for Morris-style approximate counters, replacing the old log 1/δ failure-term by a log-log 1/δ dependence and showing this is optimal. Key tools are geometric/Zi decomposition, MGF/subgamma concentration bounds, and an information-complexity direct-sum lower bound based on Braverman Garg Woodruff. Implements a practical variant with a one-line deterministic prefix fix that keeps space to the stated bound and matches theory in experiments.

AI-written summary · about

" chapters (11)

1. 0:00Welcome and introductions
2. 2:10Workshop overview
3. 5:02Introduction to approximate counting
4. 6:53Motivation for Morris counting
5. 11:07Basic randomized counters
6. 14:10Optimizing memory and variance
7. 17:02New algorithms and lower bounds
8. 22:36Analysis of the improved algorithm
9. 30:04Refining the Morris counter
10. 34:48Proving lower bounds
11. 39:49K-fold counting and conclusion