Algorithms and Hardness for Linear Algebra on Geometric Graphs

For a function K: Rd× Rd→ R≥0, and a set P = x1,..., xn ⊂ Rdof n points, the K graph GP of P is the complete graph on n nodes where the weight between nodes i and j is given by K(xi, xj). In this paper, we initiate the study of when efficient spectral graph theory is possible on these graphs. We investigate whether or not it is possible to solve the following problems in n1+o(1)time for a K-graph GP when : (a) Multiply a given vector by the adjacency matrix or Laplacian matrix of GP (b) Find a spectral sparsifier of GP (c) Solve a Laplacian system in GP's Laplacian matrix For each of these problems, we consider all functions of the form K(u, v)=f(||u-v||22) for a function f: R→ R. We provide algorithms and comparable hardness results for many such K, including the Gaussian kernel, Neural tangent kernels, and more. For example, in dimension d=Ω(logn), we show that there is a parameter associated with the function f for which low parameter values imply n1+o(1)time algorithms for all three of these problems and high parameter values imply the nonexistence of subquadratic time algorithms assuming Strong Exponential Time Hypothesis (SETH), given natural assumptions on f. As part of our results, we also show that the exponential dependence on the dimension d in the celebrated fast multi-pole method of Greengard and Rokhlin cannot be improved, assuming SETH, for a broad class of functions f. To the best of our knowledge, this is the first formal limitation proven about fast multipole methods.