A note on randomized mutual search

In Mutual Search, recently introduced by Buhrman et al. (1998), static agen ts are searching for each other: each agent is assigned one of n locations, and the computations proceed by agents sending queries from their location to other locations, until one of the queries arrives at the other agent. T he cost of a search is the number of queries made. The best known bounds fo r randomized protocols using private coins are (1) a protocol with worst-ca se expected cost of [(n + 1)/2], and (2) a lower bound of (n - 1)/8 queries for randomized protocols which make only a bounded number of coin-tosses. In this paper we strictly improve the lower bound, and present a new upper bound for shared random coins. Specifically, we first prove that the worst- case expected cost of any randomized protocol for two-agent mutual search i s at least (Ir + 1)/3. This is an improvement both in terms of number of qu eries and in terms of applicability. We also give a randomized algorithm fo r mutual search with worst-case expected cost of (n + 1)/3. This algorithm works under the assumption that the agents share a random bit string. This bound shows that no better lower bound can be obtained using our technique. (C) 1999 Published by Elsevier Science B.V. All rights reserved.