Eulerian walkers on $\mathbb{Z}^2$ have range exponent $2/3$

arXiv:2608.23545 2026 Sampling 1 ideas extracted · analyzed Aug 29, 2026

What the math gives to ML

The paper provides an operational deterministic analogue of random-walk exploration: local cyclic rotor updates generate a globally constrained trajectory, and the circuit map gives an order-independent way to expand explored sets. The transferable asset is not the specific t^{1/3} exponent, which is tied to the square lattice, but the abelian-style routing and bounded-discrepancy visitation induced by cyclic local state. This can replace independently restarted random-walk neighborhood sampling in graph neural networks with a stateful sampler that systematically covers neighborhoods while preserving a controllable exploration budget. The main test is whether this reduces minibatch sampling variance and improves validation accuracy at equal sampled edges, rather than merely producing a different traversal.

Ideas from this paper

Unverified 2026

Rotor-Router Neighborhood Sampler

Replace independently sampled random-walk paths used for GNN neighbor or subgraph sampling by persistent rotor walks on the training graph. Each node stores a pointer into a fixed cyclic ordering of its outgoing neighbors; every visit advances the pointer and selects the next neighbor, producing deterministic coverage with no repeated random choices. Use several short rotor trajectories per seed and periodically reinitialize only the rotors in an encountered subgraph.

Useful5/10
Difficulty4/10
Novelty6/10
Paper: Eulerian walkers on $\mathbb{Z}^2$ have range exponent $2/3$ arXiv:2608.23545