Sub-Linear Time Algorithms: Fast, Cheap and (Only a Little) Out of Control

on YouTube ↗01h 37m

" summary

Claims that many global questions about huge data are answerable with sublinear work: property testing of lists (a one/epsilon·log n tester that binary-searches sampled items and is optimal), fast approximations (deterministic 2-approx diameter in O(M) for M points), and distribution tests based on collision probability estimator giving ~√n/ε^2 samples for uniformity, n^{2/3} for two unknowns, and n/log n for closeness; tools include sampling, binary search, collision statistics, and local/distributed algorithm techniques (LCAs) that probe small neighborhoods.

AI-written summary · about

" chapters (22)

1. 0:00Introduction
2. 0:40The Small World Phenomenon
3. 3:28The Gold Standard
4. 9:18Example
5. 16:25Proposed Algorithm
6. 24:15Test
7. 25:35Binary Search
8. 27:27Binary Search Proof
9. 28:35Test Restated
10. 30:25Binary Search Example
11. 33:00Property Testers
12. 34:30Homomorphisms
13. 38:15Properties of Functions
14. 39:20Properties of Graphs
15. 40:05Graph isomorphism
16. 43:20Simple Example
17. 43:55Input Size
18. 45:00Algorithm
19. 48:05Large outputs
20. 49:00Local Decoding
21. 51:05Local Computation
22. 53:00Lazy Greedy