Theory Seminar - Algorithms and Hardness for Linear Algebra on Geometric Graphs, Aaron Schild

Theory Seminar - Algorithms and Hardness for Linear Algebra on Geometric Graphs, Aaron Schild

Paul G. Allen School via YouTube Direct link

Conclusion

18 of 18

18 of 18

Conclusion

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. 1 Intro
  2. 2 The n-body problem (gravitation)
  3. 3 body as adjacency matrix-vector multiplication
  4. 4 Fast multipole method (FMM) (GR87)
  5. 5 Remainder of the Talk
  6. 6 Outline of FMM (GR87)
  7. 7 Background: Well-separated pairs decomposition (WSPD)
  8. 8 Callahan-Kosaraju construction of 2-WSPD on X
  9. 9 h= f and A, B are arbitrary
  10. 10 Can FMM be improved?
  11. 11 Background strong exponential time hypothesis (SETH)
  12. 12 Background: approximate nearest neighbors
  13. 13 Hardness part 1
  14. 14 Hardness Summary
  15. 15 Open problem 1: when does FMM apply?
  16. 16 Other problems we studied
  17. 17 Open problem 2: graph problems we didn't study
  18. 18 Conclusion

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.