Speaker:  Stefan Dobrev, University of Ottawa 
Time:     Wednesday, February 13, 1:00 p.m.
Place:    room: MCD 318, SITE, University of Ottawa
Title:    Using Busy Signal to Speed-up Mutual Search

abstract:
We consider the following problem (first introduced in
\cite{Vital}): Alice and Bob check separately into the same (huge)
hotel and are given different rooms. They want to contact each
other, but for obvious reasons they don't want to draw any
attention to their relation. Hence they decide to use only the
phones available in their rooms. They can call any room within the
hotel, but they don't know each other's room number. What to do?

The authors of \cite{Vital} present a strategy how to minimize the
number of phone calls Alice and Bob make; they show that for
$N$-room hotel the number of calls can be reduced from naive $2N$
to $0.586N$, however the time complexity can be as bad as
$O(N^2)$.

We consider their approach misled, as Alice and Bob surely don't
want to spend all their youth calling hotel rooms; they want to
find each other as fast as possible, not worrying about the number
of calls.

The crucial property of phone communication the authors of
\cite{Vital} ignored is the potential presence of the busy signal.
We show that by intelligent use of busy signal Alice and Bob can
find each other in $O(\log N)$ time steps. Moreover, we show that
$O(\log N)$ time steps are enough to solve also more general
problem: There are $k$ agents in the hotel. The goal of each agent
is to find whereabouts of all other agents.