We define and construct a novel pseudorandom tool, the Markovian hitter. Given an input sequence of n independent random bits, a Markovian hitter produces a sequence of pseudorandom samples in {0, 1}k, in an online fashion, that hits any subset W ⊂ {0, 1}k of size ∊2k with probability ≈ 1 – 2–(n–k)∊. This is comparable to the behavior of truly random samples or classical pseudorandom hitting sets. A Markovian hitter has an additional “Markovian” property of interest: each pseudorandom sample is a function of only the O(k) most recent bits of the input sequence (of random bits). Such Markovian properties are useful in distributed online settings. In particular, we apply Markovian hitters to obtain a new algorithm for the well-studied blind rendezvous problem for cognitive radios. This is the problem faced by two parties equipped with radios that can access channels in potentially different subsets, S1 and S2, of a universe of n channels. Their challenge is to discover each other (by tuning their radios to the same channel at the same time) as quickly as possible. In prior work [3] it was shown that deterministic schedules have a lower bound for rendezvous time of Ω(|S1| · |S2|). We beat this quadratic barrier by utilizing a public source of randomness in conjunction with a Markovian hitter to achieve rendezvous in expected time We counterbalance this result by establishing two lower bounds on expected rendezvous time: an bound for the setting with public randomness, and an Ω(|S1| · |S2|) bound in the setting with private randomness but no public randomness, which is a strengthening of the result for deterministic schedules.

Real-world networks often consist of multiple layers, be they infrastructure such as airline networks or social such as collaboration networks. A common aspect to these networks is that there are multiple sub-networks that evolve in parallel on the same node set -- these are referred to as multiplex networks. For example, in the case of airline networks, the cities (nodes) have been well-established for several decades if not centuries, but over time new airlines (sub-networks) emerge and each airline creates its own flight linkages between cities. Similarly multiple modalities of communications evolve in parallel between individuals (nodes) such as E-mail, SMS, and Online Social Networks, e.g., Facebook and Twitter. While in some multiplex networks, each layer evolves independently from other layers over time, in other multiple networks, the evolution of a layer is coupled with that of other layers -- a process referred to as co-evolution.