93 citations · 537 across the 73 of their papers we have counts for
9 papers · 1 filter
Minor Sparsifiers and the Distributed Laplacian Paradigm
Sebastian Forster, Gramoz Goranci, Yang P. Liu +3
We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrice…
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
Monika Henzinger, Billy Jin, Richard Peng +1
Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems whose coefficient matrix is the Laplacian matrix of a we…
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai +5
We present an -time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, a…
A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices
Jiezhong Qiu, Chi Wang, Ben Liao +2
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a regular (aperiodic and irreducible) finite Markov chain. Specially, consider a random walk o…
Vertex Sparsification for Edge Connectivity
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit +5
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether -approximate cut-prese…
Solving Sparse Linear Systems Faster than Matrix Multiplication
Richard Peng, Santosh Vempala
Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph structured linear systems, in the general se…