  Blind rendezvous is a fundamental problem in cognitive radio networks. The
problem involves a collection of agents (radios) that wish to discover each
other in the blind setting where there is no shared infrastructure and they
initially have no knowledge of each other. Time is divided into discrete slots;
spectrum is divided into discrete channels, $\{1,2,..., n\}$. Each agent may
access a single channel in a single time slot and we say that two agents
rendezvous when they access the same channel in the same time slot. The model
is asymmetric: each agent $A_i$ may only use a particular subset $S_i$ of the
channels and different agents may have access to different subsets of channels.
The goal is to design deterministic channel hopping schedules for each agent so
as to guarantee rendezvous between any pair of agents with overlapping channel
sets.
  Two independent sets of authors, Shin et al. and Lin et al., gave the first
constructions guaranteeing asynchronous blind rendezvous in $O(n^2)$ and
$O(n^3)$ time, respectively. We present a substantially improved construction
guaranteeing that any two agents, $A_i$, $A_j$, will rendezvous in $O(|S_i|
|S_j| \log\log n)$ time. Our results are the first that achieve nontrivial
dependence on $|S_i|$, the size of the set of available channels. This allows
us, for example, to save roughly a quadratic factor over the best previous
results in the important case when channel subsets have constant size. We also
achieve the best possible bound of $O(1)$ time for the symmetric situation;
previous works could do no better than $O(n)$. Using the probabilistic method
and Ramsey theory we provide evidence in support of our suspicion that our
construction is asymptotically optimal for small size channel subsets: we show
both a $c |S_i||S_j|$ lower bound and a $c \log\log n$ lower bound when $|S_i|,
|S_j| \leq n/2$.
