Czumaj, Artur, Kontogeorgiou, George and Paterson, Mike (2023) Haystack hunting hints and locker room communication. Random Structures & Algorithms, 62 (4). pp. 832-856. doi:10.1002/rsa.21114 ISSN 1042-9832.
Preview |
PDF
WRAP-Haystack-hunting-hints-and-locker-room-communication-Kontogeogiou-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1MB) | Preview |
Abstract
We want to efficiently find a specific object in a large unstructured set, which we model by a randomn-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 target object? We show that by providing advice of just one integer in {0,1,...,n-1}, one can improve the success probability considerably, by a θ(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 random permutations related to the rencontres number.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
| Library of Congress Subject Headings (LCSH): | Permutations, Mathematical analysis , Computer programming, Algorithms |
| Journal or Publication Title: | Random Structures & Algorithms |
| Publisher: | John Wiley & Sons, Inc. |
| ISSN: | 1042-9832 |
| Official Date: | July 2023 |
| Dates: | Date Event July 2023 Published 31 August 2022 Available 6 June 2022 Accepted 28 May 2021 Submitted |
| Volume: | 62 |
| Number: | 4 |
| Number of Pages: | 25 |
| Page Range: | pp. 832-856 |
| DOI: | 10.1002/rsa.21114 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Open Access (Creative Commons open licence) |
| Date of first compliant deposit: | 19 October 2022 |
| Date of first compliant Open Access: | 19 October 2022 |
| RIOXX Funder/Project Grant: | Project/Grant ID RIOXX Funder Name Funder ID EP/V01305X/1 [EPSRC] Engineering and Physical Sciences Research Council Doctoral Training Partnership [EPSRC] Engineering and Physical Sciences Research Council |
| URI: | https://wrap.warwick.ac.uk/170329/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |