← 研踪 PaperTrailarXiv:2611.08705 · v1
Faster Treasure Hunt via Strongly Universal Exploration with Polylogarithmic Overhead
首次提交 2026-11-06 05:02
版本更新 2026-11-06 05:02
雷达观测 2026-11-09 10:16
摘要
We study deterministic exploration and delayed-activation treasure hunt in anonymous undirected port-labeled graphs with incoming-port information. From polynomial-time constructible ordinary universal exploration sequences of length \(O(n^c)\) for a fixed regular degree, we construct a single infinite strongly universal exploration sequence with cover time \(O(n^c\log^2n)\). Summable dyadic insertion schedules yield the sharper bound \(O_\eps(n^c\log n(\log\log n)^{1+\eps})\) for every fixed \(\eps>0\), together with refinements at every fixed iterated-logarithm depth. The proof combines reversible excursions, neutral guards and an arbitrary-window argument that treats both orientations simultaneously. For this recurrence, uniform linear expansion is equivalent to convergence of the normalized period sum. Exact counting identities also permit direct instruction access. With a logspace ordinary generator, table-free enumeration of decreasing scale paths computes instruction \(t\) using \(O(\log(t+2))\) working bits and time polynomial in \(t\). The earlier polynomial-slack bounds follow as corollaries. A local cubic simulation extends the treasure-hunt application to arbitrary-degree graphs, with the \(2m\)-vertex replacement size included explicitly in the bound.
作者备注：27 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-06 05:02 · 最新观测版本
Faster Treasure Hunt via Strongly Universal Exploration with Polylogarithmic Overhead
We study deterministic exploration and delayed-activation treasure hunt in anonymous undirected port-labeled graphs with incoming-port information. From polynomial-time constructible ordinary universal exploration sequences of length \(O(n^c)\) for a fixed regular degree, we construct a single infinite strongly universal exploration sequence with cover time \(O(n^c\log^2n)\). Summable dyadic insertion schedules yield the sharper bound \(O_\eps(n^c\log n(\log\log n)^{1+\eps})\) for every fixed \(\eps>0\), together with refinements at every fixed iterated-logarithm depth. The proof combines reversible excursions, neutral guards and an arbitrary-window argument that treats both orientations simultaneously. For this recurrence, uniform linear expansion is equivalent to convergence of the normalized period sum. Exact counting identities also permit direct instruction access. With a logspace ordinary generator, table-free enumeration of decreasing scale paths computes instruction \(t\) using \(O(\log(t+2))\) working bits and time polynomial in \(t\). The earlier polynomial-slack bounds follow as corollaries. A local cubic simulation extends the treasure-hunt application to arbitrary-degree graphs, with the \(2m\)-vertex replacement size included explicitly in the bound.
查看此版本解读 →查看此版本原文 ↗