This course explores algorithms and hardness for linear algebra on geometric graphs, specifically focusing on efficient spectral graph theory on dense \k graphs. The learning outcomes include understanding how to multiply a vector by the adjacency matrix of a graph, finding spectral sparsifiers, and solving Laplacian systems in a graph's Laplacian matrix. The course teaches algorithms and comparable hardness results for various functions of the form \k(u,v) = f(\|u-v\|_2), with a particular emphasis on the dimension d=Ω(logn). The teaching method involves presenting algorithms and hardness results for these problems, with a joint work presentation included. The intended audience for this course includes individuals interested in theoretical computer science, spectral graph theory, and algorithms for geometric graphs.
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
