Gaussian Free Fields and Computing the Cover Time
summary
Proves that cover time is captured by the Gaussian free field: cover time ≍ |E| · E[max(GFF)]^2 up to small error terms and universal constants, implying blanket time is within a constant of cover time and resolving prior log log n gaps. Proof combines the generalized Ray–Knight isomorphism with a continuous refinement (replace edges by intervals, run Brownian motion) and a coupling that gives stochastic domination of local times by level sets of the GFF. Also shows nearly-linear sampling via Laplacian solvers to compute the estimator.
AI-written summary · about
chapters (12)
- 0:00Introduction to cover time
- 1:32Defining the cover time
- 3:51Graph theory questions
- 7:48Spectral methods on the torus
- 11:00Generalizing spectral results
- 14:17Structural properties
- 17:34Error term analysis
- 20:50Gaussian free field connection
- 27:30Isomorphism theorem overview
- 33:33Isomorphism theorem proofs
- 41:05Conjecture and domination
- 46:46Continuity and conclusion
related talks
24mExact Covering with Colours
57mQuery Optimization and Evaluation 1: Output Size Bounds and Information Theory
35mDistributed Models for Private Analysis of Graph Data
47mSublinear Time Eigenvalue Approximation via Random Sampling
18mFast Inference for Probabilistic Graphical Models
33mLinear and sublinear algorithms for graphlet sampling
01h 02mCounting Subgraphs in Sublinear Time
43mResizable Sketches