pith. sign in

arxiv: 1906.10530 · v1 · pith:GNI6MLIDnew · submitted 2019-06-24 · 💻 cs.DS

Fully Dynamic Spectral Vertex Sparsifiers and Applications

David Durfee , Yu Gao , Gramoz Goranci , Richard Peng This is my paper

Pith reviewed 2026-05-25 17:22 UTC · model grok-4.3

classification 💻 cs.DS
keywords dynamic algorithmsspectral sparsifiersLaplacian systemseffective resistancevertex sparsifiersdata structuresgraph algorithmssublinear time
0
0 comments X

The pith

A data structure maintains spectral vertex sparsifiers under edge insertions, deletions, and terminal additions in sublinear time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a data structure for maintaining spectral vertex sparsifiers of graphs with respect to a chosen set of terminals. These sparsifiers preserve pairwise resistances, solutions to linear systems, and energies of electrical flows between the terminals. The structure supports edge insertions, deletions, and terminal additions in sublinear time. It is applied to maintain approximate solutions to Laplacian systems on bounded-degree unweighted graphs and all-pairs effective resistances, providing the first sublinear-time data structures for these Laplacian primitives without assumptions on graph topologies.

Core claim

The authors construct a fully dynamic data structure for spectral vertex sparsifiers with respect to a set of terminals that supports insertions and deletions of edges and terminal additions in sublinear time. This is used to maintain ε-approximate solutions to Laplacian systems Lx = b with access to approximate energies and vectors, as well as (1 ± ε)-approximations to all-pairs effective resistances under intermixed updates and queries, all in sublinear amortized time on unweighted and weighted graphs against an oblivious adversary.

What carries the argument

Spectral vertex sparsifier with respect to terminals, which preserves pairwise resistances, solutions to linear systems, and energies of electrical flows between the terminals.

If this is right

  • Enables maintenance of approximate solutions to Laplacian systems with Õ(n^{11/12} ε^{-5}) expected amortized update and query time for bounded-degree unweighted graphs.
  • Supports (1 ± ε)-approximations to all-pairs effective resistance queries with Õ(min(m^{3/4}, n^{5/6} ε^{-2}) ε^{-4}) time on unweighted graphs and Õ(n^{5/6} ε^{-6}) on weighted graphs.
  • Provides the first sublinear-time dynamic maintenance of key Laplacian paradigm primitives without assumptions on underlying graph topologies.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The terminal-based sparsifier approach may allow dynamic versions of other problems that reduce to Laplacian solves or resistance computations.
  • Sublinear dynamic resistance maintenance could support incremental algorithms for network reliability or clustering tasks.
  • The oblivious-adversary setting leaves open whether similar bounds hold against adaptive adversaries.

Load-bearing premise

The sublinear bounds and approximation guarantees rely on the existence of efficient static spectral sparsifiers and other prior results from the Laplacian paradigm, with the graph assumed bounded-degree and unweighted for the Laplacian application and resistance queries assuming an oblivious adversary.

What would settle it

An explicit sequence of edge insertions, deletions, and terminal additions on a bounded-degree unweighted graph where the data structure either exceeds the stated amortized update time or fails to return an ε-approximate Laplacian solution vector or energy within the claimed bound.

Figures

Figures reproduced from arXiv: 1906.10530 by David Durfee, Gramoz Goranci, Richard Peng, Yu Gao.

Figure 1
Figure 1. Figure 1: A weighted graph on which a random walk takes a long t [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗
Figure 2
Figure 2. Figure 2: An instance of the graph described in Definition A.2 [PITH_FULL_IMAGE:figures/full_fig_p046_2.png] view at source ↗
read the original abstract

We study \emph{dynamic} algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals $T$ of our choice. Such objects preserve pairwise resistances, solutions to systems of linear equations, and energy of electrical flows between the terminals in $T$. We give a data structure that supports insertions and deletions of edges, and terminal additions, all in sublinear time. Our result is then applied to the following problems. (1) A data structure for maintaining solutions to Laplacian systems $\mathbf{L} \mathbf{x} = \mathbf{b}$, where $\mathbf{L}$ is the Laplacian matrix and $\mathbf{b}$ is a demand vector. For a bounded degree, unweighted graph, we support modifications to both $\mathbf{L}$ and $\mathbf{b}$ while providing access to $\epsilon$-approximations to the energy of routing an electrical flow with demand $\mathbf{b}$, as well as query access to entries of a vector $\tilde{\mathbf{x}}$ such that $\left\lVert \tilde{\mathbf{x}}-\mathbf{L}^{\dagger} \mathbf{b} \right\rVert_{\mathbf{L}} \leq \epsilon \left\lVert \mathbf{L}^{\dagger} \mathbf{b} \right\rVert_{\mathbf{L}}$ in $\tilde{O}(n^{11/12}\epsilon^{-5})$ expected amortized update and query time. (2) A data structure for maintaining All-Pairs Effective Resistance. For an intermixed sequence of edge insertions, deletions, and resistance queries, our data structure returns $(1 \pm \epsilon)$-approximation to all the resistance queries against an oblivious adversary with high probability. Its expected amortized update and query times are $\tilde{O}(\min(m^{3/4},n^{5/6} \epsilon^{-2}) \epsilon^{-4})$ on an unweighted graph, and $\tilde{O}(n^{5/6}\epsilon^{-6})$ on weighted graphs. These results represent the first data structures for maintaining key primitives from the Laplacian paradigm for graph algorithms in sublinear time without assumptions on the underlying graph topologies.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces fully dynamic data structures for maintaining spectral vertex sparsifiers with respect to a chosen terminal set T. These support edge insertions/deletions and terminal additions in sublinear time while preserving pairwise resistances, Laplacian system solutions, and electrical flow energies between terminals. Applications include (1) a data structure maintaining ε-approximate solutions to Lx=b (energy and vector entries) in Õ(n^{11/12}ε^{-5}) expected amortized time for bounded-degree unweighted graphs, and (2) all-pairs effective resistance maintenance returning (1±ε)-approximations in Õ(min(m^{3/4},n^{5/6}ε^{-2})ε^{-4}) time (unweighted, oblivious adversary) or Õ(n^{5/6}ε^{-6}) (weighted). The work claims to be the first sublinear dynamic maintenance of Laplacian-paradigm primitives without assumptions on graph topologies.

Significance. If the sublinear bounds and approximation guarantees hold, the results advance dynamic graph algorithms by providing the first sublinear-time data structures for spectral vertex sparsifiers and their Laplacian applications, extending the static Laplacian paradigm to fully dynamic settings while preserving key primitives such as resistance distances and approximate linear-system solutions.

major comments (2)
  1. [Abstract] Abstract: the central claim that the results are the 'first data structures for maintaining key primitives from the Laplacian paradigm for graph algorithms in sublinear time without assumptions on the underlying graph topologies' is undercut by the explicit bounded-degree unweighted requirement stated for application (1) to obtain the Õ(n^{11/12}ε^{-5}) bound; this assumption is load-bearing because the vertex-sparsifier maintenance and resistance preservation may lose sublinearity or require higher cost when maximum degree is unbounded.
  2. [Abstract] Abstract: the all-pairs resistance result is restricted to an oblivious adversary, which is an assumption on the update/query sequence not mentioned in the 'without assumptions on the underlying graph topologies' phrasing and is load-bearing for the claimed high-probability guarantees.
minor comments (1)
  1. [Abstract] The abstract would be clearer if it explicitly distinguished the general vertex-sparsifier result from the additional assumptions required by each listed application.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive comments on the abstract. We address each major comment below and will revise the abstract accordingly to improve precision.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the results are the 'first data structures for maintaining key primitives from the Laplacian paradigm for graph algorithms in sublinear time without assumptions on the underlying graph topologies' is undercut by the explicit bounded-degree unweighted requirement stated for application (1) to obtain the Õ(n^{11/12}ε^{-5}) bound; this assumption is load-bearing because the vertex-sparsifier maintenance and resistance preservation may lose sublinearity or require higher cost when maximum degree is unbounded.

    Authors: We agree that the abstract phrasing would benefit from greater precision. The bounded-degree unweighted assumption applies specifically to the runtime bound in application (1); the core spectral vertex sparsifier data structure and its resistance-preservation properties hold for general graphs (with the degree bound used only to obtain the stated sublinear time). The phrase 'without assumptions on the underlying graph topologies' is meant to exclude restrictions such as planarity or bounded treewidth rather than to claim degree-independent runtimes. To eliminate ambiguity we will revise the abstract to explicitly qualify the central claim with the per-application assumptions. revision: yes

  2. Referee: [Abstract] Abstract: the all-pairs resistance result is restricted to an oblivious adversary, which is an assumption on the update/query sequence not mentioned in the 'without assumptions on the underlying graph topologies' phrasing and is load-bearing for the claimed high-probability guarantees.

    Authors: The abstract already states that the all-pairs resistance data structure works 'against an oblivious adversary with high probability.' The phrase 'without assumptions on the underlying graph topologies' refers to the input graph rather than the adversary model. Nevertheless, to make the summary claim fully accurate we will revise the abstract so that the central claim also acknowledges the oblivious-adversary setting required for the high-probability guarantee. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The paper presents new dynamic data structures for maintaining spectral vertex sparsifiers and applies them to Laplacian systems and resistance queries. It explicitly relies on the existence of efficient static spectral sparsifiers and other prior Laplacian paradigm results as external inputs, without any equations or claims that reduce the new dynamic bounds or approximations to fitted parameters, self-definitions, or self-citation chains by construction. The bounded-degree assumption is stated explicitly for one application and does not create a self-referential loop. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the work relies on standard mathematical assumptions in dynamic algorithms and prior results in the Laplacian paradigm; no free parameters, invented entities, or ad-hoc axioms are visible.

axioms (2)
  • domain assumption Existence of efficient static spectral sparsifiers from prior work.
    Implicitly used to achieve the dynamic maintenance.
  • domain assumption Oblivious adversary model for update sequences in resistance queries.
    Explicitly stated for the all-pairs resistance application.

pith-pipeline@v0.9.0 · 5923 in / 1164 out tokens · 32430 ms · 2026-05-25T17:22:06.543396+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

84 extracted references · 84 canonical work pages · 2 internal anchors

  1. [1]

    Fully dynamic all-pairs shortest paths with worst-case update-time revisited

    Ittai Abraham, Shiri Chechik, and Sebastian Krinninger . Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Symposium on Discrete Algorithms (SODA) , pages 440–452, 2017

    work page 2017

  2. [2]

    On fully dynamic graph sparsifiers

    Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In Symposium on Foundations of Computer Science (FOCS) , pages 335–344, 2016

    work page 2016

  3. [3]

    Aleliunas, R

    R. Aleliunas, R. J. Lipton, L. Lovasz, C. Rackoff, and R. M. Karp. Random walks, universal traversal sequences, and the complexity of maze problems. I n Symposium on Foundations of Computer Science (FOCS) , pages 218–223, 1979

    work page 1979

  4. [4]

    Towards (1 + ǫ)-approximate flow sparsifiers

    Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. Towards (1 + ǫ)-approximate flow sparsifiers. In Symposium on Discrete algorithms (SODA) , pages 279–293, 2014

    work page 2014

  5. [5]

    On solving linear systems in sublinear time

    Alexandr Andoni, Robert Krauthgamer, and Yosef Pogrow. On solving linear systems in sublinear time. In Innovations in Theoretical Computer Science Conference (I TCS), pages 3:1–3:19, 2019. 40

    work page 2019

  6. [6]

    Short random walks on graphs

    Greg Barnes and Uriel Feige. Short random walks on graphs. SIAM Journal on Discrete Mathemathics, 9(1):19–28, 1996

    work page 1996

  7. [7]

    Fully dyn amic maximal matching in O(log n) update time

    Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dyn amic maximal matching in O(log n) update time. SIAM Journal on Computing , 44(1):88–113, 2015. Announced at FOCS’11

    work page 2015

  8. [8]

    F ully dynamic randomized algo- rithms for graph spanners

    Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. F ully dynamic randomized algo- rithms for graph spanners. ACM Transactions on Algorithms (TALG) , 8(4):35, 2012

    work page 2012

  9. [9]

    Spielman, Nikhil Srivastava, an d Shang-Hua Teng

    Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, an d Shang-Hua Teng. Spectral sparsi- fication of graphs: theory and algorithms. Communications of the ACM , 56(8):87–94, August 2013

    work page 2013

  10. [10]

    Benczur and David R

    Andras A. Benczur and David R. Karger. Approximating s-t minimum cuts in ˜O(n2) time. In Symposium on Theory of computing (STOC) , pages 47–55, 1996

    work page 1996

  11. [11]

    Deterministic decre mental single source shortest paths: beyond the O(mn) bound

    Aaron Bernstein and Shiri Chechik. Deterministic decre mental single source shortest paths: beyond the O(mn) bound. In Symposium on Theory of Computing (STOC) , pages 389–397, 2016

    work page 2016

  12. [12]

    New deterministic approxi- mation algorithms for fully dynamic matching

    Sayan Bhattacharya, Monika Henzinger, and Danupon Nano ngkai. New deterministic approxi- mation algorithms for fully dynamic matching. In Symposium on Theory of Computing (STOC) , pages 398–411, 2016

    work page 2016

  13. [13]

    Vertex sparsifiers and abstract rounding algorithms

    Moses Charikar, Tom Leighton, Shi Li, and Ankur Moitra. Vertex sparsifiers and abstract rounding algorithms. In Symposium on Foundations of Computer Science (FOCS) , pages 265– 274, 2010

    work page 2010

  14. [14]

    Efficient sampling for Gaussian graphical models via spectral sparsification

    Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang- Hua Teng. Efficient sampling for Gaussian graphical models via spectral sparsification. Conference on Learning Theory (COLT), pages 364–390, 2015

    work page 2015

  15. [15]

    Italiano

    Camil Demetrescu and Giuseppe F. Italiano. A new approa ch to dynamic all pairs shortest paths. J. ACM , 51(6):968–992, 2004

    work page 2004

  16. [16]

    Kron reduction of gr aphs with applications to electrical networks

    Florian Dörfler and Francesco Bullo. Kron reduction of gr aphs with applications to electrical networks. IEEE Trans. on Circuits and Systems , 60-I(1):150–163, 2013

    work page 2013

  17. [17]

    Doyle and J

    Peter G. Doyle and J. Laurie Snell. Random Walks and Electric Networks , volume 22 of Carus Mathematical Monographs. Mathematical Association of America, 1984

    work page 1984

  18. [18]

    Sampling ran- dom spanning trees faster than matrix multiplication

    David Durfee, Rasmus Kyng, John Peebles, Anup B Rao, and Sushant Sachdeva. Sampling ran- dom spanning trees faster than matrix multiplication. In Symposium on Theory of Computing (STOC), pages 730–742, 2017

    work page 2017

  19. [19]

    David Durfee, John Peebles, Richard Peng, and Anup B. Rao . Determinant-preserving spar- sification of SDDM matrices with applications to counting an d sampling spanning trees. In Symposium on Foundations of Computer Science (FOCS) , pages 926–937, 2017

    work page 2017

  20. [20]

    Offline algorithms for dynamic minimum s panning tree problems

    David Eppstein. Offline algorithms for dynamic minimum s panning tree problems. In Workshop on Algorithms and Data Structures (W ADS) , pages 392–399, 1991. 41

    work page 1991

  21. [21]

    Sparsification: a technique for speeding up dynamic graph algorithms

    David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amn on Nissenzweig. Sparsification: a technique for speeding up dynamic graph algorithms. Journal of the ACM , 44(5):669–696,

    work page

  22. [22]

    Announced at FOCS’92

    work page

  23. [23]

    A tight bound on approximating arbi- trary metrics by tree metrics

    Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbi- trary metrics by tree metrics. J. Comput. Syst. Sci. , 69(3):485–497, 2004

    work page 2004

  24. [24]

    Data structures for on-line updat ing of minimum spanning trees, with applications

    Greg N Frederickson. Data structures for on-line updat ing of minimum spanning trees, with applications. SIAM Journal on Computing , 14(4):781–798, 1985. Announced at STOC’84

    work page 1985

  25. [25]

    The pow er of vertex sparsifiers in dynamic graph algorithms

    Gramoz Goranci, Monika Henzinger, and Pan Peng. The pow er of vertex sparsifiers in dynamic graph algorithms. In European Symposium on Algorithms (ESA) , pages 45:1–45:14, 2017

    work page 2017

  26. [26]

    Dynami c effective resistances and approx- imate schur complement on separable graphs

    Gramoz Goranci, Monika Henzinger, and Pan Peng. Dynami c effective resistances and approx- imate schur complement on separable graphs. In European Symposium on Algorithms (ESA) , pages 40:1–40:15, 2018

    work page 2018

  27. [27]

    I ncremental exact min-cut in poly- logarithmic amortized update time

    Gramoz Goranci, Monika Henzinger, and Mikkel Thorup. I ncremental exact min-cut in poly- logarithmic amortized update time. In European Symposium on Algorithms (ESA) , pages 46:1–46:17, 2016

    work page 2016

  28. [28]

    Dynamic low- stretch trees via dy- namic low-diameter decompositions

    Gramoz Goranci and Sebastian Krinninger. Dynamic low- stretch trees via dy- namic low-diameter decompositions. CoRR, abs/1804.04928, 2018. A vailable at: http://arxiv.org/abs/1804.04928

    work page arXiv 2018

  29. [29]

    Fully dynamic (1 +ǫ)-approximate matchings

    Manoj Gupta and Richard Peng. Fully dynamic (1 +ǫ)-approximate matchings. In Symposium on Foundations of Computer Science (FOCS) , pages 548–557, 2013

    work page 2013

  30. [30]

    Decremental single-source shortest paths on undirected graphs in near-linear total up date time

    Monika Henzinger, Sebastian Krinninger, and Danupon N anongkai. Decremental single-source shortest paths on undirected graphs in near-linear total up date time. In Symposium on Foun- dations of Computer Science (FOCS) , pages 146–155, 2014

    work page 2014

  31. [31]

    Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and der andomization

    Monika Henzinger, Sebastian Krinninger, and Danupon N anongkai. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and der andomization. SIAM Journal on Computing, 45(3):947–1006, 2016. Announced at FOCS’13

    work page 2016

  32. [32]

    A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex c onnectivity

    Monika Rauch Henzinger. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex c onnectivity. Journal of Algorithms , 24(1):194–220, 1997

    work page 1997

  33. [33]

    Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spann ing tree, 2-edge, and biconnectivity

    Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup . Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spann ing tree, 2-edge, and biconnectivity. Journal of the ACM , 48(4):723–760, 2001. Announced at STOC’98

    work page 2001

  34. [34]

    Faster fully-dynamic minimum span- ning forest

    Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum span- ning forest. In European Symposium on Algorithms (ESA) , pages 742–753, 2015

    work page 2015

  35. [35]

    Density independent al- gorithms for sparsifying k-step random walks

    Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sa wlani. Density independent al- gorithms for sparsifying k-step random walks. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPR OX), pages 14:1–14:17, 2017

    work page 2017

  36. [36]

    Dynamic gr aph connectivity in polylog- arithmic worst case time

    Bruce M Kapron, Valerie King, and Ben Mountjoy. Dynamic gr aph connectivity in polylog- arithmic worst case time. In Symposium on Discrete Algorithms (SODA) , pages 1131–1142, 2013. 42

    work page 2013

  37. [37]

    Kelner, Yin Tat Lee, Lorenzo Orecchia, and A aron Sidford

    Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and A aron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generaliza- tions. In Symposium on Discrete Algorithms (SODA) , pages 217–226, 2014

    work page 2014

  38. [38]

    Faster sp ectral sparsification and numerical algorithms for SDD matrices

    Ioannis Koutis, Alex Levin, and Richard Peng. Faster sp ectral sparsification and numerical algorithms for SDD matrices. ACM Transactions on Algorithms , 12(2):17:1–17:16, 2016

    work page 2016

  39. [39]

    Miller, and Richard Peng

    Ioannis Koutis, Gary L. Miller, and Richard Peng. A near ly-m log n time solver for SDD linear systems. In Symposium on Foundations of Computer Science (FOCS) , pages 590–598, 2011

    work page 2011

  40. [40]

    Mimicking networks and succinct representations of terminal cuts

    Robert Krauthgamer and Inbal Rika. Mimicking networks and succinct representations of terminal cuts. In Symposium on Discrete algorithms (SODA) , pages 1789–1799, 2013

    work page 2013

  41. [41]

    Spar- sified cholesky and multigrid solvers for connection laplac ians

    Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdev a, and Daniel A Spielman. Spar- sified cholesky and multigrid solvers for connection laplac ians. In Symposium on Theory of Computing (STOC) , pages 842–850, 2016

    work page 2016

  42. [42]

    Approximate gaussia n elimination for laplacians-fast, sparse, and simple

    Rasmus Kyng and Sushant Sachdeva. Approximate gaussia n elimination for laplacians-fast, sparse, and simple. In Symposium on Foundations of Computer Science (FOCS) , pages 573– 582, 2016

    work page 2016

  43. [43]

    Min-cuts and shortest cycles in planar graphs in o (n loglogn) time

    Jakub Lacki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in o (n loglogn) time. In European Symposium on Algorithms (ESA) , pages 155–166, 2011

    work page 2011

  44. [44]

    Kirchhoff index as a measure o f edge centrality in weighted networks: Nearly linear time algorithms

    Huan Li and Zhongzhi Zhang. Kirchhoff index as a measure o f edge centrality in weighted networks: Nearly linear time algorithms. In Symposium on Discrete Algorithms (SODA) , pages 2377–2396, 2018

    work page 2018

  45. [45]

    Kleinberg

    David Liben-Nowell and Jon M. Kleinberg. The link predi ction problem for social networks. In International Conference on Information and Knowledge Man agement (CIKM), pages 556–559, 2003

    work page 2003

  46. [46]

    Graph reduction with spectral and cut guarantees

    Andreas Loukas. Graph reduction by local variation. CoRR, abs/1808.10650, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  47. [47]

    Spectrally a pproximating large graphs with smaller graphs

    Andreas Loukas and Pierre Vandergheynst. Spectrally a pproximating large graphs with smaller graphs. In ICML, volume 80 of JMLR Workshop and Conference Proceedings, pages 3243–3252. JMLR.org, 2018

    work page 2018

  48. [48]

    Fast approximation algorithms for c ut-based problems in undirected graphs

    Aleksander Madry. Fast approximation algorithms for c ut-based problems in undirected graphs. In Symposium on Foundations of Computer Science (FOCS) , pages 245–254, 2010

    work page 2010

  49. [49]

    Fast generation of random span- ning trees and the effective resistance metric

    Aleksander Madry, Damian Straszak, and Jakub Tarnawsk i. Fast generation of random span- ning trees and the effective resistance metric. In Symposium on Discrete Algorithms (SODA) , pages 2019–2036, 2015

    work page 2019

  50. [50]

    Metric ext ension operators, vertex sparsifiers and lipschitz extendability

    Konstantin Makarychev and Yury Makarychev. Metric ext ension operators, vertex sparsifiers and lipschitz extendability. In Symposium on Foundations of Computer Science (FOCS) , pages 255–264, 2010

    work page 2010

  51. [51]

    Miller and Richard Peng

    Gary L. Miller and Richard Peng. Approximate maximum flo w on separable undirected graphs. In Symposium on Discrete Algorithms (SODA) , pages 1151–1170, 2013. 43

    work page 2013

  52. [52]

    Approximation algorithms for multicomm odity-type problems with guarantees independent of the graph size

    Ankur Moitra. Approximation algorithms for multicomm odity-type problems with guarantees independent of the graph size. In Symposium on Foundations of Computer Science (FOCS) , pages 3–12, 2009

    work page 2009

  53. [53]

    Dynamic spanning forest with worst-case update time: adaptive, las vegas, and O(n1/ 2− ǫ)-time

    Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and O(n1/ 2− ǫ)-time. In Symposium on Theory of Computing (STOC), pages 1122–1129, 2017

    work page 2017

  54. [54]

    Dynamic minimum spanning forest with subpolynomial worst-case update time

    Danupon Nanongkai, Thatchaphol Saranurak, and Christ ian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time . In Symposium on Foundations of Computer Science (FOCS) , pages 950–961, 2017

    work page 2017

  55. [55]

    Simple deterministic alg orithms for fully dynamic maximal matching

    Ofer Neiman and Shay Solomon. Simple deterministic alg orithms for fully dynamic maximal matching. ACM Trans. Algorithms , 12(1):7:1–7:15, 2016. Announced at STOC’13

    work page 2016

  56. [56]

    Maintaining a lar ge matching and a small vertex cover

    Krzysztof Onak and Ronitt Rubinfeld. Maintaining a lar ge matching and a small vertex cover. In Symposium on Theory of computing (STOC) , pages 457–464, 2010

    work page 2010

  57. [57]

    Graph spanners

    David Peleg and Alejandro A Schäffer. Graph spanners. Journal of graph theory , 13(1):99–116, 1989

    work page 1989

  58. [58]

    Optimal Offline Dynamic $2,3$-Edge/Vertex Connectivity

    Richard Peng, Bryce Sandlund, and Daniel Dominic Sleato r. Offline dynamic higher connec- tivity. CoRR, abs/1708.03812, 2017. A vailable at: http://arxiv.org/a bs/1708.03812

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  59. [59]

    Spielman

    Richard Peng and Daniel A. Spielman. An efficient paralle l solver for SDD linear systems. In Symposium on Theory of Computing (STOC) , pages 333–342, 2014

    work page 2014

  60. [60]

    Optimal hierarchical decompositions fo r congestion minimization in networks

    Harald Räcke. Optimal hierarchical decompositions fo r congestion minimization in networks. In Symposium on Theory of computing (STOC) , pages 255–264, 2008

    work page 2008

  61. [61]

    Dynamic transitive closure via dynam ic matrix inverse (extended abstract)

    Piotr Sankowski. Dynamic transitive closure via dynam ic matrix inverse (extended abstract). In Symposium on Foundations of Computer Science (FOCS) , pages 509–517, 2004

    work page 2004

  62. [62]

    An almost-linear time algorithm for unif orm random spanning tree generation

    Aaron Schild. An almost-linear time algorithm for unif orm random spanning tree generation. In Symposium on Theory of Computing (STOC) , pages 214–227, 2018

    work page 2018

  63. [63]

    Local ization of electrical flows

    Aaron Schild, Satish Rao, and Nikhil Srivastava. Local ization of electrical flows. In Symposium on Discrete Algorithms (SODA) , pages 1577–1584, 2018

    work page 2018

  64. [64]

    Nearly maximum flows in nearly linear tim e

    Jonah Sherman. Nearly maximum flows in nearly linear tim e. In Symposium on Foundations of Computer Science (FOCS) , pages 263–269, 2013

    work page 2013

  65. [65]

    Fully dynamic maximal matching in consta nt update time

    Shay Solomon. Fully dynamic maximal matching in consta nt update time. In Foundations of Computer Science (FOCS) , pages 325–334, 2016

    work page 2016

  66. [66]

    Spielman and S

    D. Spielman and S. Teng. Spectral sparsification of grap hs. SIAM Journal on Computing , 40(4):981–1025, 2011

    work page 2011

  67. [67]

    Spielman and S

    D. Spielman and S. Teng. Nearly linear time algorithms f or preconditioning and solving sym- metric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applica- tions, 35(3):835–885, 2014

    work page 2014

  68. [68]

    Graph sparsific ation by effective resistances

    Daniel Spielman and Nikhil Srivastava. Graph sparsific ation by effective resistances. SIAM Journal on Computing , 40(6):1913–1926, 2011. 44

    work page 1913

  69. [69]

    Spielman

    Daniel A. Spielman. Algorithms, Graph Theory, and Line ar Equations in Laplacian Matrices. In Proceedings of the International Congress of Mathematicia ns, 2010

    work page 2010

  70. [70]

    The Laplacian Paradigm: Emerging Algo rithms for Massive Graphs

    Shang-Hua Teng. The Laplacian Paradigm: Emerging Algo rithms for Massive Graphs. In Theory and Applications of Models of Computation , pages 2–14, 2010

    work page 2010

  71. [71]

    Fully-dynamic min-cut

    Mikkel Thorup. Fully-dynamic min-cut. Combinatorica, 27(1):91–127, 2007. Announced at STOC’01

    work page 2007

  72. [72]

    Joel A. Tropp. User-friendly tail bounds for sums of ran dom matrices. Foundations of Com- putational Mathemathics , 12(4):389–434, August 2012

    work page 2012

  73. [73]

    Semi-supervised learning on data streams via temporal label propagation

    Tal Wagner, Sudipto Guha, Shiva Prasad Kasiviswanatha n, and Nina Mishra. Semi-supervised learning on data streams via temporal label propagation. In International Conference on Machine Learning (ICML) , pages 5082–5091, 2018

    work page 2018

  74. [74]

    Fully-dynamic minimum spanni ng forest with improved worst-case update time

    Christian Wulff-Nilsen. Fully-dynamic minimum spanni ng forest with improved worst-case update time. In Symposium on Theory of Computing (STOC) , pages 1130–1143, 2017. A Lower Bound on Load of Edge We show that our bound on the maximum load of a vertex from Lemm a 5.5 is close to tight. This bound is crucial for bounding the effect of a single insertion /d...

    work page 2017

  75. [75]

    Let G be a bounded-degree graph of constant expansion on k vertices, denoted as the core

    work page

  76. [76]

    For our overall bound on the number of steps that a random walk takes in the core component, we need the following bound on the expected number of steps of a walk within each ray

    Extend G by adding for each core vertex u, a path of length k/ 10, denoted as the ‘ray’ of u. For our overall bound on the number of steps that a random walk takes in the core component, we need the following bound on the expected number of steps of a walk within each ray. Lemma A.3. The probability that a random walk starting from one end of a p ath reac...

    work page

  77. [77]

    Simulate a random walk starting from u until it first hits T at vertex t1,

    work page

  78. [78]

    Simulate a random walk starting from v until it first hits T at vertex t2,

    work page

  79. [79]

    , u ℓ = t2), where ℓ is the length of the combined walk

    Combine these two walks (including e) to get a walk u = (t1 = u0, . . . , u ℓ = t2), where ℓ is the length of the combined walk

    work page

  80. [80]

    Note that this rescaling by 1/ρ (∑ 1≤ i≤ ℓ 1 w wi− 1wi ) is quite natural: Consider the degenerate case where T = V

    Add the edge (t1, t 2) to H with weight 1/ ( ρ ℓ− 1∑ i=0 ( 1/ w uiui+1 ) ) The resulting graph H satisfies LH≈ ǫ SC(G, T ) with high probability. Note that this rescaling by 1/ρ (∑ 1≤ i≤ ℓ 1 w wi− 1wi ) is quite natural: Consider the degenerate case where T = V . This routine generates ρ copies of each edge, which then need to be rescaled by 1/ρ to ensure ...

    work page

Showing first 80 references.