View ann-vertex,m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with thelengths of random walks on the graph. For example, thecommute time between two verticess andt (the expected length of a random walk froms tot and back) is precisely characterized by the effective resistanceR st betweens andt: commute time=2mR st . As a corollary, thecover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistanceR in the graph to within a factor of logn:mR<-cover time<-O(mRlogn). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, we improve known bounds on cover times for high-degree graphs and expanders, and give new proofs of known results for multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.

Ashok K. Chandra

Prabhakar Raghavan

Walter L. Ruzzo

Roman Smolensky

Prasoon Tiwari

Computational Complexity

计算复杂性提出了计算复杂性方面的杰出研究。它的主题是数学和理论计算机科学之间的接口，具有清晰的数学轮廓和严格的数学格式。中心主题是：计算模型、复杂性界限（特别强调下界）、复杂性类别、权衡结果用于确定性、概率性和非确定性计算的“一般”（布尔）和“结构化”计算（例如决策树、算术电路）的顺序和并行计算最坏情况和平均情况的具体重点领域包括：复杂性类别的结构（简化、相对化问题、度，去随机化）代数复杂性（双线性复杂性，多项式、组、代数和表示的计算）交互式证明、伪随机生成和随机性提取复杂性问题：密码学学习理论数论逻辑（逻辑理论的复杂性，决策过程的成本）组合优化和近似解分布式计算性能测试。

The journal 'Computational Complexity' is dedicated to outstanding research in the field of computational complexity, focusing on the interface between mathematics and theoretical computer science, characterized by clear mathematical outlines and rigorous mathematical formats. The central themes include computational models, complexity bounds (with a particular emphasis on lower bounds), complexity classes, and trade-off results for deterministic, probabilistic, and non-deterministic computations. Specific areas of focus include: the structure of complexity classes (simplification, relativization problems, degrees, derandomization), algebraic complexity (bilinear complexity, computations of polynomials, groups, algebras, and representations), interactive proofs, pseudorandom generation, and randomness extraction. Complexity issues encompass cryptography, learning theory, number theory, logic (the complexity of logical theories, costs of decision processes), combinatorial optimization and approximate solutions, as well as performance testing in distributed computing.

《Computational Complexity》期刊致力于计算复杂性领域的杰出研究，涵盖数学与理论计算机科学之间的接口，具有清晰的数学轮廓和严格的数学格式。其核心主题包括计算模型、复杂性界限（特别是下界）、复杂性类别，以及用于确定性、概率性和非确定性计算的权衡结果。具体重点领域包括：复杂性类别的结构（简化、相对化问题、度，去随机化）、代数复杂性（双线性复杂性、多项式、组、代数和表示的计算）、交互式证明、伪随机生成和随机性提取。复杂性问题涉及密码学、学习理论、数论、逻辑（逻辑理论的复杂性、决策过程的成本）、组合优化和近似解，以及分布式计算性能测试。

The electrical resistance of a graph captures its commute and cover times

Known relations between random walks and electrical networks are extended by showing that resistance in this network is intimately connected with the lengths of random walks on the graph, and bounds on cover time obtained are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix.

Category	Quartile
计算机科学	3
计算机科学, 计算机理论方法	3
计算机科学, 数学	3

The electrical resistance of a graph captures its commute and cover times

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info