{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T04:54:20Z","timestamp":1692507260380},"reference-count":16,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T00:00:00Z","timestamp":1661904000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100015065","name":"Centre for Discrete Mathematics and its Applications, University of Warwick","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100015065","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V01305X\/1"],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2023,7]]},"abstract":"Abstract<\/jats:title>We want to efficiently find a specific object in a large unstructured set, which we model by a random<\/jats:italic>\u00a0\u2010permutation<\/jats:italic>, 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 . 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 , one can improve the success probability considerably, by a 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.<\/jats:p>","DOI":"10.1002\/rsa.21114","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T11:52:22Z","timestamp":1661946742000},"page":"832-856","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Haystack hunting hints and locker room communication"],"prefix":"10.1002","volume":"62","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[{"name":"Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP) University of Warwick Coventry UK"}]},{"given":"George","family":"Kontogeorgiou","sequence":"additional","affiliation":[{"name":"Mathematics Institute University of Warwick Coventry UK"}]},{"given":"Mike","family":"Paterson","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP) University of Warwick UK"}]}],"member":"311","published-online":{"date-parts":[[2022,8,31]]},"reference":[{"key":"e_1_2_10_2_1","doi-asserted-by":"crossref","unstructured":"M.Adler S.Chakrabarti M.Mitzenmacher andL. E.Rasmussen.Parallel randomized load balancing. Proc. 27th Annu. ACM Symp. Theory of Computing (STOC) 1995 pp. 238\u2013247.","DOI":"10.1145\/225058.225131"},{"key":"e_1_2_10_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"e_1_2_10_4_1","first-page":"3","article-title":"Teoria statistica delle classi e calcolo delle probabilit\u00e0","volume":"8","author":"Carlo Emilio Bonferroni","year":"1936","journal-title":"Pubbl. R Ist. Sup. Sci. Econ. Commer. Fir."},{"key":"e_1_2_10_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03025323"},{"key":"e_1_2_10_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2018.1418100"},{"key":"e_1_2_10_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02986999"},{"key":"e_1_2_10_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M"},{"key":"e_1_2_10_9_1","doi-asserted-by":"crossref","unstructured":"Anna G\u00e1l and Peter Bro Miltersen.The cell probe complexity of succinct data structures. Proc. 30th Annu. Int. Colloquium on Automata Languages and Programming (ICALP) 2003 332\u2013344.","DOI":"10.1007\/3-540-45061-0_28"},{"key":"e_1_2_10_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20068"},{"key":"e_1_2_10_11_1","volume-title":"Concrete mathematics: A Foundation for Computer Science","author":"Graham R. L.","year":"1994"},{"key":"e_1_2_10_12_1","volume-title":"The art of computer programming: Sorting and searching","author":"Knuth D. E.","year":"1998"},{"key":"e_1_2_10_13_1","volume-title":"Probability and computing: Randomized and probabilistic techniques in algorithms and data analysis","author":"Mitzenmacher M.","year":"2017"},{"key":"e_1_2_10_14_1","doi-asserted-by":"crossref","unstructured":"M.RaabandA.Steger.\u201cBalls into bins\u201d\u2014A simple and tight analysis. Proc. 2nd Int. Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM) 1998 159\u2013170.","DOI":"10.1007\/3-540-49543-6_13"},{"key":"e_1_2_10_15_1","volume-title":"An introduction to combinatorial analysis","author":"Riordan J.","year":"1958"},{"issue":"4","key":"e_1_2_10_16_1","first-page":"260, 285, 289","article-title":"Names in boxes puzzle","volume":"37","author":"Winkler P.","year":"2006","journal-title":"College Math. J."},{"key":"e_1_2_10_17_1","volume-title":"Mathematical mind\u2010benders","author":"Winkler P.","year":"2007"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21114","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/rsa.21114","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T01:22:11Z","timestamp":1692494531000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.21114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,31]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.1002\/rsa.21114"],"URL":"https:\/\/doi.org\/10.1002\/rsa.21114","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,31]]},"assertion":[{"value":"2021-05-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-06","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}