# Algorithms and Hardness for Linear Algebra on Geometric Graphs

arXiv: https://arxiv.org/abs/2011.02466 · HTML: https://mlsanity.com/paper/2011.02466/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2020.

## Built on by (most cited first, 22 of 22)

- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [Training Tensor Attention Efficiently: From Cubic to Almost Linear Time](https://mlsanity.com/paper/2405.16411/) (2024)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory](https://mlsanity.com/paper/2208.03915/) (2022)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (2023)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [The Complexity of Dynamic Least-Squares Regression](https://mlsanity.com/paper/2201.00228/) (2022)
- [Fast Approximation of Similarity Graphs with Kernel Density Estimation](https://mlsanity.com/paper/2310.13870/) (2023)
- [Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products](https://mlsanity.com/paper/2311.01960/) (2023)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Even Faster Kernel Matrix Linear Algebra via Density Estimation](https://mlsanity.com/paper/2510.02540/) (2025)
- [Graph Enabled Cross-Domain Knowledge Transfer](https://mlsanity.com/paper/2304.03452/) (2023)
- [Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser](https://mlsanity.com/paper/2305.06541/) (2023)
- [Tracking High-order Evolutions via Cascading Low-rank Fitting](https://mlsanity.com/paper/2604.10980/) (2026)

## Abstract (arXiv)

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.