For a class of dense graphs generated from geometric points in d dimensions, we show almost-input-time algorithms and fine-grained hardness results for tasks ranging from matrix-vector multiplication, spectral sparsifier construction, and Laplacian system solving.
As a consequence of our work, we show fast algorithms to perform maximum flow, sparse cut, and effective resistance computation quickly on such graphs.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.
