2026-07-22T10:24:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14127 2024-03-06T10:53:32Z ddc:004 open_access

Haystack Hunting Hints and Locker Room Communication Czumaj, Artur Kontogeorgiou, George Paterson, Mike Random permutations Search Communication complexity 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 to select the element at random, and achieve the success probability 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 Θ((log n)/(log log n)) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Artur Czumaj and George Kontogeorgiou and Mike Paterson 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.58 urn:nbn:de:0030-drops-141270 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.58 eng https://creativecommons.org/licenses/by/4.0/legalcode