Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers

on YouTube ↗27m

" summary

Proves new non‑adaptive lower bounds in the cell‑probe model using the sunflower lemma: treat each element’s accessed cell set, find a sunflower with P ≈ n^{1/(tI+tM)} petals, and show the core's contents compress a random middle‑third subset. Concludes that when inserts are non‑adaptive the median time satisfies tM ≥ n^{1/tI}, and when both operations are non‑adaptive the times obey tI+tM = Ω(log n) (constants hidden by word size and model assumptions).

AI-written summary · about

" chapters (16)

1. 0:00Start
2. 4:54Cell Probe Model [Yao81]
3. 6:39Non-Adaptive Inserts
4. 6:56Adaptive Median
5. 7:11Non-Adaptive Predecessors
6. 7:33Some Known Dynamic Data Structure Lower Bounds
7. 8:32Non-Adaptive Lower Bounds Minimum with deletions
8. 12:18Results for Median in Other Models
9. 12:57Sunflower Lemma [ErdosRado60]
10. 14:15First Lower Bound for Median
11. 14:48Outline of Rbdfine of Proof
12. 17:06Proof of Theorem 1
13. 21:51Second Lower Bound for Median
14. 22:54Reduction to kth smallest
15. 24:25The Chronogram Approach [FS89] [PT14]
16. 25:14Chronogram Proof