English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider a search problem on trees in which an agent starts at the root of a tree and aims to locate an adversarially placed treasure, by moving along the edges, while relying on local, partial information. Specifically, each node in the tree holds a pointer to one of its neighbors, termed advice. A node is faulty with probability q. The advice at a non-faulty node points to the neighbor that is closer to the treasure, and the advice at a faulty node points to a uniformly random neighbor. Crucially, the advice is permanent, in the sense that querying the same node again would yield the same answer. Let Δ denote the maximum degree. For the expected number of moves (edge traversals) until finding the treasure, we show that a phase transition occurs when the noise parameter q is roughly 1 √Δ. Below the threshold, there exists an algorithm with expected number of moves O(D √Δ), where D is the depth of the treasure, whereas above the threshold, every search algorithm has an expected number of moves, which is both exponential in D and polynomial in the number of nodes n. In contrast, if we require to find the treasure with probability at least 1 − δ, then for every fixed ɛ > 0, if q < 1/Δɛ, then there exists a search strategy that with probability 1 − δ finds the treasure using (Δ −1D)O(1/ε) moves. Moreover, we show that (Δ −1D)Ω(1/ε) moves are necessary.

Navigating in Trees with Permanently Noisy Advice