Completed
Background: approximate nearest neighbors
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Theory Seminar - Algorithms and Hardness for Linear Algebra on Geometric Graphs, Aaron Schild
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 The n-body problem (gravitation)
- 3 body as adjacency matrix-vector multiplication
- 4 Fast multipole method (FMM) (GR87)
- 5 Remainder of the Talk
- 6 Outline of FMM (GR87)
- 7 Background: Well-separated pairs decomposition (WSPD)
- 8 Callahan-Kosaraju construction of 2-WSPD on X
- 9 h= f and A, B are arbitrary
- 10 Can FMM be improved?
- 11 Background strong exponential time hypothesis (SETH)
- 12 Background: approximate nearest neighbors
- 13 Hardness part 1
- 14 Hardness Summary
- 15 Open problem 1: when does FMM apply?
- 16 Other problems we studied
- 17 Open problem 2: graph problems we didn't study
- 18 Conclusion
