Premium
Haystack hunting hints and locker room communication
Author(s) -
Czumaj Artur,
Kontogeorgiou George,
Paterson Mike
Publication year - 2023
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21114
Subject(s) - haystack , permutation (music) , random permutation , set (abstract data type) , matching (statistics) , task (project management) , object (grammar) , computer science , integer (computer science) , advice (programming) , element (criminal law) , coin flipping , theoretical computer science , mathematics , algorithm , combinatorics , statistics , artificial intelligence , engineering , symmetric group , physics , systems engineering , acoustics , law , political science , programming language
We want to efficiently find a specific object in a large unstructured set, which we model by a random n $$ 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 to select the element at random, and achieve the success probability1 n$$ \frac{1}{n} $$ . Can we do better with some small amount of advice about the permutation, even without knowing the target object? We show that by providing advice of just one integer in{ 0 , 1 , … , n − 1 } $$ \left\{0,1,\dots, n-1\right\} $$ , one can improve the success probability considerably, by aΘ ( log n log log n ) $$ \Theta \left(\frac{\log n}{\mathrm{loglog}n}\right) $$ 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 random permutations related to the rencontres number.