Self-Improving Algorithms for Sorting and Geometric Problems

on YouTube ↗43m

" summary

Comparison based algorithms learn a product distribution (each Xi independent) and build per-input entropy-optimal search trees plus a small “typical set” V (constructed by taking about λ ≈ log n samples and sampling every λ-th value). For sorting and Delaunay triangulation the preprocessing (roughly n^{1+α} storage/training with a 1/α time tradeoff; baseline O(n^2) training/storage) yields expected running time O(n + H(output)) and outputs linear-time verifiable certificates of correctness. Convex hull and maxima use the same ideas but hulls need extra work (best bound n log log n + H(output)).

AI-written summary · about

" chapters (12)

1. 0:00Introduction and context
2. 1:53Defining the problem
3. 4:48Technical setup and hurdles
4. 6:46Strategy for algorithm design
5. 8:20Problems and certificates
6. 12:09Comparison-based bounds
7. 15:17Entropy optimal search trees
8. 16:40Distributional constraints
9. 20:55Sorting algorithm analysis
10. 27:27Geometric algorithms
11. 32:08Complexity and specific cases
12. 40:52Concluding remarks