# 1 Search Results for "Cai, Dongrun"

Document
##### Effective Resistances in Non-Expander Graphs

Authors: Dongrun Cai, Xue Chen, and Pan Peng

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

##### Abstract
Effective resistances are ubiquitous in graph algorithms and network analysis. For an undirected graph G, its effective resistance R_G(s,t) between two vertices s and t is defined as the equivalent resistance between s and t if G is thought of as an electrical network with unit resistance on each edge. If we use L_G to denote the Laplacian matrix of G and L_G^† to denote its pseudo-inverse, we have R_G(s,t) = (𝟏_s-𝟏_t)^⊤ L^† (𝟏_s-𝟏_t) such that classical Laplacian solvers [Daniel A. Spielman and Shang{-}Hua Teng, 2014] provide almost-linear time algorithms to approximate R_G(s,t). In this work, we study sublinear time algorithms to approximate the effective resistance of an adjacent pair s and t. We consider the classical adjacency list model [Ron, 2019] for local algorithms. While recent works [Andoni et al., 2018; Peng et al., 2021; Li and Sachdeva, 2023] have provided sublinear time algorithms for expander graphs, we prove several lower bounds for general graphs of n vertices and m edges: 1) It needs Ω(n) queries to obtain 1.01-approximations of the effective resistance of an adjacent pair s and t, even for graphs of degree at most 3 except s and t. 2) For graphs of degree at most d and any parameter 𝓁, it needs Ω(m/𝓁) queries to obtain c ⋅ min{d,𝓁}-approximations where c > 0 is a universal constant. Moreover, we supplement the first lower bound by providing a sublinear time (1+ε)-approximation algorithm for graphs of degree 2 except the pair s and t. One of our technical ingredients is to bound the expansion of a graph in terms of the smallest non-trivial eigenvalue of its Laplacian matrix after removing edges. We discover a new lower bound on the eigenvalues of perturbed graphs (resp. perturbed matrices) by incorporating the effective resistance of the removed edge (resp. the leverage scores of the removed rows), which may be of independent interest.

##### Cite as

Dongrun Cai, Xue Chen, and Pan Peng. Effective Resistances in Non-Expander Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 29:1-29:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

```@InProceedings{cai_et_al:LIPIcs.ESA.2023.29,
author =	{Cai, Dongrun and Chen, Xue and Peng, Pan},
title =	{{Effective Resistances in Non-Expander Graphs}},
booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
pages =	{29:1--29:18},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-295-2},
ISSN =	{1868-8969},
year =	{2023},
volume =	{274},
editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.29},
URN =		{urn:nbn:de:0030-drops-186823},
doi =		{10.4230/LIPIcs.ESA.2023.29},
annote =	{Keywords: Sublinear Time Algorithm, Effective Resistance, Leverage Scores, Matrix Perturbation}
}```
• Refine by Author
• 1 Cai, Dongrun
• 1 Chen, Xue
• 1 Peng, Pan

• Refine by Classification
• 1 Theory of computation → Streaming, sublinear and near linear time algorithms

• Refine by Keyword
• 1 Effective Resistance
• 1 Leverage Scores
• 1 Matrix Perturbation
• 1 Sublinear Time Algorithm

• Refine by Type
• 1 document

• Refine by Publication Year
• 1 2023

X

Feedback for Dagstuhl Publishing