Haystack Hunting Hints and Locker Room Communication

Artur Czumaj, George Kontogeorgiou, Mike Paterson

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. Clea…