DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2021.58

Haystack Hunting Hints and Locker Room Communication

Authors: Artur Czumaj, George Kontogeorgiou, and Mike Paterson

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

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.

Cite as

Artur Czumaj, George Kontogeorgiou, and Mike Paterson. Haystack Hunting Hints and Locker Room Communication. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 58:1-58:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{czumaj_et_al:LIPIcs.ICALP.2021.58,
  author =	{Czumaj, Artur and Kontogeorgiou, George and Paterson, Mike},
  title =	{{Haystack Hunting Hints and Locker Room Communication}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{58:1--58:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.58},
  URN =		{urn:nbn:de:0030-drops-141270},
  doi =		{10.4230/LIPIcs.ICALP.2021.58},
  annote =	{Keywords: Random permutations, Search, Communication complexity}
}

Search Results

Documents authored by Paterson, Mike

Haystack Hunting Hints and Locker Room Communication

Abstract

Cite as

Thanks for your feedback!

Could not send message