Online Search With a Hint
summary
Explores linear search with untrusted hints and gives concrete tradeoffs: exact-position hints admit a shrunk exponential strategy that is Pareto-optimal; direction hints use a biased geometric strategy and an extension of Gall’s functional lemma to prove optimality and show the doubling strategy is uniquely optimal for average 9. Quantitative tradeoffs appear: to get robustness 9 consistency can be ≈6.6 (drops to ≈6.19 by robustness 10), and a proven one-bit lower bound forces consistency ≥5 for any non-robust strategy.
AI-written summary · about