Algorithms and Hardness for Linear Algebra on Geometric Graphs

For a function mathsfK : ℝd × ℝd → ℝ≥ 0, and a set P = x1, ldots, xn subset ℝd of n points, the mathsfK graph GP of P is the complete graph on n nodes where the weight between nodes i and j is given by mathsfK(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 mathsfK-graph GP when d < no(1): bullet Multiply a given vector by the adjacency matrix or Laplacian matrix of GP bullet Find a spectral sparsifier of GP bullet Solve a Laplacian system in GP's Laplacian matrix For each of these problems, we consider all functions of the form mathsfK(u,v) = f(|u-v|22) for a function f:ℝ rightarrow ℝ. We provide algorithms and comparable hardness results for many such mathsfK, including the Gaussian kernel, Neural tangent kernels, and more. For example, in dimension d = Omega(log n), 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 (mathsfSETH), 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 multipole method of Greengard and Rokhlin cannot be improved, assuming mathsfSETH, for a broad class of functions f. To the best of our knowledge, this is the first formal limitation proven about fast multipole methods.