The Library
Haystack hunting hints and locker room communication
Tools
Tools
Tools
Czumaj, Artur, Kontogeorgiou, George and Paterson, Michael S. (2021) Haystack hunting hints and locker room communication. In: 48th International Colloquium on Automata, Languages and Programming (ICALP 2021), Virtual, Scotland, 12-16 Jul 2021. Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198 58 : 1-58: 20. ISBN 9783959771955. ISSN 1868-8969. doi:10.4230/LIPIcs.ICALP.2021.58
|
PDF
WRAP-Haystack-hunting-hints-locker-room-communication-Czumaj-2021.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1657Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.58
Abstract
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.
| Item Type: | Conference Item (Paper) | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) 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, Computational complexity, Machine theory -- Mathematical models, Discrete mathematics | |||||||||||||||
| Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||||||||
| Journal or Publication Title: | 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) | |||||||||||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||||||||
| ISBN: | 9783959771955 | |||||||||||||||
| ISSN: | 1868-8969 | |||||||||||||||
| Official Date: | 2 July 2021 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Volume: | 198 | |||||||||||||||
| Page Range: | 58 : 1-58: 20 | |||||||||||||||
| DOI: | 10.4230/LIPIcs.ICALP.2021.58 | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Access rights to Published version: | Open Access | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||
| Title of Event: | 48th International Colloquium on Automata, Languages and Programming (ICALP 2021) | |||||||||||||||
| Type of Event: | Conference | |||||||||||||||
| Location of Event: | Virtual, Scotland | |||||||||||||||
| Date(s) of Event: | 12-16 Jul 2021 | |||||||||||||||
| Related URLs: | ||||||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
