Treasure hunt

For a treasure present when the agent starts, Ta-Shma and Zwick note that following \(U_1U_2U_4\dots\), universal traversal sequences of doubling length, solves the problem in polynomial time Ta-Shma & Zwick 2014. The bounds above are for the harder case. All three are proved for \(\Delta\)-regular graphs with fixed \(\Delta \ge 3\), where \(\theta\) is defined; Ta-Shma and Zwick reach arbitrary degrees by self-loops up to degree \(n\) Ta-Shma & Zwick 2014, and Xin by a cubic simulation whose bound is in \(m\) Xin 2026, so the three exponents compare directly only on regular graphs. Ta-Shma and Zwick build the strongly universal exploration sequence by inserting, after the \(i\)-th symbol of an ordinary one, a forward and a backward copy of a much shorter prefix whose length is about the square root of the 2-adic part of \(i\); walking a sequence and then its reverse returns the agent to where it was, so every window of length \(O(n^{2\theta})\) contains a full universal sequence for \(n\) nodes Ta-Shma & Zwick 2014. Xin first shrank the inserted prefixes to a \(1/a\) power Xin 2007, and later chose them by periods \(q_j \approx 2^j j(\log j)^{1+\varepsilon}\) with \(\sum_j 2^j/q_j\) finite, which keeps the whole sequence within a constant factor of the ordinary one and gives windows of length \(O(n^{\theta}\log n\,(\log\log n)^{1+\varepsilon})\) (preprint) Xin 2026. In that preprint the agent computes the \(t\)-th instruction with \(O(\log(t+2))\) bits of memory, so its memory grows with the time since it started, not with the graph Xin 2026. Checked against the full texts (Xin 2026: arXiv v1).