Explore algorithms and hardness results for linear algebra on geometric graphs in this theory seminar. Delve into efficient spectral graph theory for k-graphs, examining problems like matrix-vector multiplication, spectral sparsification, and Laplacian system solving. Investigate the relationship between function parameters and algorithmic efficiency, considering SETH-based hardness results. Learn about the limitations of the fast multipole method and its dimensional dependence. Gain insights into well-separated pairs decomposition, approximate nearest neighbors, and open problems in the field of geometric graph algorithms.
Theory Seminar - Algorithms and Hardness for Linear Algebra on Geometric Graphs, Aaron Schild
Paul G. Allen School via YouTube
Overview
Syllabus
Intro
The n-body problem (gravitation)
body as adjacency matrix-vector multiplication
Fast multipole method (FMM) (GR87)
Remainder of the Talk
Outline of FMM (GR87)
Background: Well-separated pairs decomposition (WSPD)
Callahan-Kosaraju construction of 2-WSPD on X
h= f and A, B are arbitrary
Can FMM be improved?
Background strong exponential time hypothesis (SETH)
Background: approximate nearest neighbors
Hardness part 1
Hardness Summary
Open problem 1: when does FMM apply?
Other problems we studied
Open problem 2: graph problems we didn't study
Conclusion
Taught by
Paul G. Allen School
