Local Access to Random Walks

on YouTube ↗19m

" summary

Provides a local-access algorithm that answers position-at-time queries on a random walk with per-query cost about (1/(1−λ))·√n (up to polylog factors), and proves a matching Ω(√n) lower bound for random d-regular graphs. The algorithm partitions time into blocks K = Θ(Tmix·log n), fixes positions at multiples of K uniformly, and fills gaps by searching for the first collision of two k/2-length walks (uses the birthday paradox), costing ~√n walk samples. The lower bound uses a structural lemma via the configuration model that <√n neighbor probes fail to find a cycle with probability ≥0.99. For abelian Cayley graphs the per-query cost drops to poly(d)·log n.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:13Big Data in Computation
3. 1:01Local Computation Algorithms
4. 2:23LCAs for Big Random Objects Even Levi Medina Rosen, Biswas Rubinfeld Yodpinaneel
5. 5:25Local Generation of Random Walks
6. 5:55Our Results: Expansion Based
7. 7:15Upper Bound: Walk Shattering
8. 8:17Analysis: Time
9. 8:53Analysis: Closeness
10. 11:11How Much Can A Learn
11. 12:45Algorithm's Eye View
12. 13:59Lower Bound: Crunch
13. 15:45Lower Bound: Closing In
14. 17:32Lower Bound: Summary