REVIEW 4 cited by
Graph Sparsification by Effective Resistances
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph $G=(V,E,w)$ and a parameter $\epsilon>0$, we produce a weighted subgraph $H=(V,\tilde{E},\tilde{w})$ of $G$ such that $|\tilde{E}|=O(n\log n/\epsilon^2)$ and for all vectors $x\in\R^V$ $(1-\epsilon)\sum_{uv\in E}(x(u)-x(v))^2w_{uv}\le \sum_{uv\in\tilde{E}}(x(u)-x(v))^2\tilde{w}_{uv} \le (1+\epsilon)\sum_{uv\in E}(x(u)-x(v))^2w_{uv}. (*)$ This improves upon the sparsifiers constructed by Spielman and Teng, which had $O(n\log^c n)$ edges for some large constant $c$, and upon those of Bencz\'ur and Karger, which only satisfied (*) for $x\in\{0,1\}^V$. A key ingredient in our algorithm is a subroutine of independent interest: a nearly-linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in $O(\log n)$ time.
Forward citations
Cited by 4 Pith papers
-
Meeting and coalescence times for random walks in the largest component of the Erd\H{o}s-R\'enyi random graph
Expected meeting, coalescence, and voter-consensus times on the Erdős–Rényi giant are Θ(n) throughout the fixed-supercritical, slightly-supercritical, and critical regimes.
-
Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model
John ellipsoid approximation in the leverage-score model achieves doubly logarithmic accuracy cost after setup by using last-iterate acceleration and Newton steps instead of averaging.
-
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
A batch-dynamic massively parallel algorithm maintains undirected graph connectivity in a constant number of communication rounds with near-linear communication per batch, alongside a P-completeness lower bound for ad...
-
Flows in Almost Linear Time via Adaptive Preconditioning
Algorithms achieve almost-linear time for ℓ_p-norm flow and dual regression problems on unit-weighted graphs for a range of p, plus applications to max-flow and total variation.
Discussion (0). Continue with ORCID to comment.