4 November 2026
Random walks: robust to cover, fragile to hit
On a huge clique with a private leaf on every vertex and one extra path of length L, an adversary nudging transition probabilities can be tolerated up to a fixed ε ≈ 0.293 before cover time doubles, but only ε ≈ 0.628/L before hitting time doubles, refuting Zuckerman's conjecture that the two tolerances always agree up to a constant.
availability and archiving · internal replay · 5 dimensions not assessed