论文标题
干草堆狩猎提示和更衣室通讯
Haystack Hunting Hints and Locker Room Communication
论文作者
论文摘要
我们希望在一个大型的非结构化集中有效地找到一个特定的对象，我们通过随机的$ n $ permunt对其进行建模，我们必须通过仅揭示一个元素来做到这一点。显然，如果没有任何帮助，此任务是无望的，最好的做法就是随机选择元素，并实现成功概率$ \ frac {1} {n} $。即使在不知道该物体寻求的情况下，我们也可以通过少量建议做得更好吗？我们表明，通过提供$ \ {0,1，...，n-1 \} $中一个整数的建议，可以通过$θ（\ frac {logn} {loglogn}）$ factor $θ（\ frac {logn}）$ factor。我们研究了这个问题和相关的问题，并显示出渐近匹配的上限和下限，以获得成功的最佳概率。
We want to efficiently find a specific object in a large unstructured set, which we model by a random $n$-permutation, and we have to do it by revealing just a single element. Clearly, without any help this task is hopeless and the best one can do is select the element at random, and achieve the success probability $\frac{1}{n}$. Can we do better with some small amount of advice about the permutation, even without knowing the object sought? We show that by providing advice of just one integer in $\{0,1,...,n-1\}$, one can improve the success probability considerably, by a $Θ(\frac{logn}{loglogn})$ factor. We study this and related problems, and show asymptotically matching upper and lower bounds for their optimal probability of success.Our analysis relies on a close relationship of such problems to some intrinsic properties of rendom permutations related to the rencontres number.
