A Brief Intro to Analysis Beyond the Worst Case

on YouTube ↗41m

" summary

Survey of concrete beyond-worst-case claims and tools across decades: semi-random graph model where random flips at noise rate P ≈ 1/√n let SDPs recover planted colorings (matching information-theoretic limits); access-graph and Markov models explain why LRU beats FIFO on practical paging workloads; smooth analysis — simplex becomes polynomial in expectation under tiny Gaussian perturbations; clustering guarantees under approximation stability (C ≈ 1.1) or perturbation resilience let algorithms provably recover near‑optimal clusterings; learning-from-samples frameworks pick the best heuristic for a given application distribution.

AI-written summary · about

" chapters (24)

1. 0:00Introduction
2. 0:13Title
3. 0:37Workshop Overview
4. 2:20The Problem
5. 3:26Average Case Analysis
6. 4:37Randomness
7. 5:44Intermediate Models
8. 6:24Fox 1990
9. 9:04Online Algorithms
10. 10:39Access Graphs
11. 11:43Loose Competitiveity
12. 12:57Intermediate Model
13. 15:16Smooth Analysis Model
14. 17:44Smooth Analysis Results
15. 18:27Nice Inputs
16. 24:05Ground Truth
17. 24:18Objective
18. 26:27Clustering Objectives
19. 27:21Perturbation Resilience
20. 29:23Optimal Solutions
21. 30:38Related Work
22. 31:33Average Case for Unknown Distribution
23. 33:04Work
24. 34:34Tractability