Algorithms and Hardness for Linear Algebra on Geometric Graphs

11/04/2020
āˆ™
by   Josh Alman, et al.
āˆ™
0
āˆ™

For a function š–Ŗ : ā„^dƗā„^dā†’ā„_ā‰„ 0, and a set P = { x_1, ā€¦, x_n}āŠ‚ā„^d of n points, the š–Ŗ graph G_P of P is the complete graph on n nodes where the weight between nodes i and j is given by š–Ŗ(x_i, x_j). 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 n^1+o(1) time for a š–Ŗ-graph G_P when d < n^o(1): āˆ™ Multiply a given vector by the adjacency matrix or Laplacian matrix of G_P āˆ™ Find a spectral sparsifier of G_P āˆ™ Solve a Laplacian system in G_P's Laplacian matrix For each of these problems, we consider all functions of the form š–Ŗ(u,v) = f(u-v_2^2) for a function f:ā„ā†’ā„. We provide algorithms and comparable hardness results for many such š–Ŗ, including the Gaussian kernel, Neural tangent kernels, and more. For example, in dimension d = Ī©(log n), we show that there is a parameter associated with the function f for which low parameter values imply n^1+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 (š–²š–¤š–³š–§), 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 š–²š–¤š–³š–§, for a broad class of functions f. To the best of our knowledge, this is the first formal limitation proven about fast multipole methods.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset