Jelani Nelson- Forty Years of Frequent Items

Explore the evolution and advancements in frequent items algorithms over the past four decades in this 46-minute lecture by Jelani Nelson for the International Mathematical Union. Delve into various aspects of the field, including change detection, turnstile streaming algorithms, and bounds for lg-heavy hitters. Examine the BPTree structure, reductions to finding super-heavy items, and the application of core lemmas. Discover the speaker's contributions, including their novel solution and main data structure. Learn about techniques such as stitching chunks as paths, using expanders for stitching, and answering HH queries. Investigate Local Differential Privacy, optimization strategies, and the utility of meta approaches. Gain insights from experimental results and explore the tradeoffs involved in frequent items algorithms.