Guus Regts

Non-Backtracking Walks Reach Collisions Near the Square-Root Scale

Expected self-intersection time is O(√n log n) on bounded-degree graphs and O(√n) for regular graphs with a uniform spectral gap.