Source-linked AI summary
Cover times, blanket times, and majorizing measures
Jian Ding, James R. Lee, Yuval Peres
TL;DR
The paper addresses open questions about graph cover and blanket times. It develops a connection characterized by a main theorem, resolves a stated conjecture for general finite-state reversible Markov chains, and gives approximation algorithms for cover time.
Problem
Basic questions about the cover time remained open, including whether it admits a deterministic polynomial-time approximation scheme up to a (1 + ε) factor.
Method
The paper develops a primary connection through a theorem for finite connected graphs and proves the preceding theorem more generally for finite-state reversible Markov chains.
Results
The work positively resolves Conjecture 1.1 and provides an O(n^ω)-time randomized algorithm, as well as a near-linear-time algorithm in the number of edges.
Takeaways & Limitations
The theorem and algorithms provide a characterization and practical approximation procedures for cover time on graphs.
Takeaways & Limitations
The asymptotic behavior of δ-blanket time as δ → 1, including the dependence on δ of A_δ, remains an open question.
Abstract
from arXiv · showhide
We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand's theory of majorizing measures. In particular, we show that the cover time of any graph $G$ is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on $G$, scaled by the number of edges in $G$. This allows us to resolve a number of open questions. We give a deterministic polynomial-time algorithm that computes the cover time to within an O(1) factor for any graph, answering a question of Aldous and Fill (1994). We also positively resolve the blanket time conjectures of Winkler and Zuckerman (1996), showing that for any graph, the blanket and cover times are within an O(1) factor. The best previous approximation factor for both these problems was $O((\log \log n)^2)$ for $n$-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).
1 Introduction
The paper connects graph cover times to Gaussian processes and majorizing measures, resolving open questions about blanket times and deterministic approximation. Its main results provide constant-factor characterizations and algorithms for cover times across graphs and reversible Markov chains.
- Main connection: A universal-constant equivalence connects cover times with majorizing-measure quantities and the Gaussian free field.The paper identifies this connection as a primary contribution and uses it to derive its main cover-time theorem.
- Blanket times: The blanket-time conjecture is resolved: for fixed δ, blanket and cover times are equivalent up to a constant depending on δ.The previous best bound for n-node graphs was O((log log n)^2), while the question of an n-independent constant remained open.
- Gaussian free field: Theorem 1.3 relates cover time to the square of the expected maximum of the Gaussian free field, scaled by the graph size through its edge count.The theorem is stated for every graph, with the Gaussian free field defined on that graph.
- Algorithms: A deterministic polynomial-time algorithm computes a constant-factor approximation to cover time by deterministically approximating the γ2 functional.The algorithm applies to finite metric spaces with polynomial-time distance computation and resolves the deterministic cover-time approximation question.
- Comparison results: The paper also establishes a comparison theorem: bounding one graph’s commute-time metric by L times another’s yields tcov(G) ≤ O(L) · tcov(G′).This transfers cover-time bounds between graphs through their commute-time distances.
- Generality: The framework extends beyond simple graphs to finite-state reversible Markov chains presented as networks with conductances.The general theorem is stated for any network and the algorithmic result covers finite-state reversible chains.
2 Gaussian processes and local times
The paper connects Gaussian processes arising from network random walks to local times, blanket times, and hitting-time geometry. These connections yield bounds for blanket times and an asymptotically strong cover-time upper bound.
- Gaussian processes and local times: The isomorphism theorem produces a Gaussian process whose covariance is explicitly related to the network's resistance metric.The associated process is tied to inverse local times and a fixed reference vertex.
- Blanket time: For fixed δ, blanket-time bounds are expressed using total conductance and the expected supremum and maximal variance of the associated Gaussian process.The continuous- and discrete-time results both state bounds in terms of Gaussian-process quantities.
- Blanket time: The blanket-time results are tight for the complete graph, while the dependence on δ as δ approaches 1 remains an open asymptotic question.The paper identifies the δ-dependence of the constant as an interesting question.
- Blanket time: The discrete-time analysis transfers continuous-time local-time estimates to the embedded jump chain, where visit counts provide the discrete analogue of local times.The proof uses exponential holding times and concentration estimates.
- Cover time: The paper gives an asymptotically strong cover-time upper bound under the assumption that maximal hitting time is o(cover time).Theorem 2.8 formulates the bound using the Gaussian free field and maximal hitting time.
3 Majorizing measures
This section develops tree and majorizing-measure representations of Gaussian-process suprema. It then establishes quantitative equivalences and a deterministic polynomial-time approximation for γ2.
- Majorizing measures: Majorizing-measure theory represents Gaussian-process suprema through metric structure, admissible partitions, and trees of subsets.Tree size depends only on the metric and provides a lower bound comparable to the expected supremum.
- Tree representations: An r-size assigns a multiscale value to trees of subsets by aggregating logarithmic branching terms along maximal branches.The definition uses the infimum over maximal branches and log+ notation.
- Majorizing measures: Theorem 3.2 connects γ2 with majorizing-measure quantities for arbitrary metric spaces.The surrounding results use this connection to compare γ2 with tree-based values.
- Tree representations: Theorem 3.3 and Lemma 3.4 show that suitable multiscale functions and separated trees provide quantitative upper bounds for γ2.The proof constructs trees from separated metric balls and concludes γ2(X,d) ≲r θ(X).
- Separated trees: Separated-tree transformations preserve tree values up to controlled factors and relate subset trees to r-separated trees.Lemma 3.10 gives the correspondence between r-size and valr, with an additive diameter term in one direction.
- Deterministic approximation: If pairwise metric distances are computable in polynomial time, the paper computes A(X,d) in polynomial time with γ2(X,d) ≍ A(X,d).The algorithm removes dependence on the number of intermediate scales by skipping duplicate maps.
4 The cover time
The cover-time analysis combines Gaussian free fields, separated trees, local times, and majorizing measures. It proves a principal cover-time theorem and derives algorithmic consequences.
- The cover-time theorem: The main cover-time proof uses the Gaussian free field and majorizing-measure theory to control local-time events associated with uncovered vertices.The argument combines first- and second-moment estimates with Gaussian-process structure.
- The cover-time theorem: Theorem 4.1 supplies the central cover-time estimate for networks in terms of total conductance and the associated Gaussian process.The proof concludes the lower bound by combining local-time estimates with the Gaussian-process construction.
- Consequences: The results also imply a positive answer to the strong blanket-time conjecture of Winkler and Zuckerman.The paper states this consequence directly after the cover-time analysis.
- The cover-time theorem: Separated trees extracted from the resistance metric supply the multiscale structure used to find leaves with Gaussian values near a target level.The proof couples leaf events to a percolation process and exploits separation for approximate independence.
- The cover-time theorem: Orthogonal decompositions of the Gaussian process organize variance contributions along root-to-leaf paths in the separated tree.The construction introduces orthogonal Gaussian increments and groups them by path intervals.
- Algorithmic consequence: For graphs, the cover-time theorem is stated through the Gaussian free field and effective-resistance geometry.The network formulation specializes to graph settings through the resistance metric.
- Algorithmic consequence: A randomized algorithm runs in O(m(log m)^O(1)) time and outputs a number whose expectation approximates the network's cover time up to universal constants.Theorem 4.14 states the guarantee for connected networks with m nonzero conductance pairs.
5 Open problems and further discussion
The discussion examines how sharply the cover-time/GFF asymptotic relation holds and poses open questions about deterministic approximation and cover-time concentration. The relation is confirmed for complete graphs and regular trees, while sharper general guarantees remain open.
- Open problems: The paper asks whether deterministic polynomial-time algorithms can approximate cover time within a (1 + ε) factor for any graph.This question was already solved for trees by Feige and Zeitouni.
- Open problems: A second question asks whether the standard deviation of τcov is bounded by thit and whether normalized deviations exhibit exponential decay at a constant rate.These questions concern sharper concentration around the expected cover time.
- Sharpness of the main relation: The asymptotic formula is stated for complete graphs and regular trees, with ηv denoting the Gaussian free field anchored at a fixed vertex.The notation an ∼ bn means an/bn converges to 1.
- Sharpness of the main relation: For complete graphs, the Gaussian free field calculation combined with tcov(Gn) ∼ n log n and |E(Gn)| = n(n−1)/2 confirms the asymptotic formula.The calculation represents the field using a shared Gaussian variable and independent vertex-specific Gaussian variables.
- Sharpness of the main relation: For regular b-ary trees, tcov(Tm) ∼ 2mn log n and E supv ηv ∼ √(2m log n), so the same asymptotic relation holds.The tree has n − 1 edges, and the discussion identifies the relation’s generality as an interesting remaining question.