  We study the classical rumor spreading problem, which is used to spread
information in an unknown network with $n$ nodes. We present the first protocol
for any expander graph $G$ with $n$ nodes and minimum degree $\Theta(n)$ such
that, the protocol informs every node in $O(\log n)$ rounds with high
probability, and uses $O(\log n\log\log n)$ random bits in total. The runtime
of our protocol is tight, and the randomness requirement of $O(\log n\log\log
n)$ random bits almost matches the lower bound of $\Omega(\log n)$ random bits.
We further study rumor spreading protocols for more general graphs, and for
several graph topologies our protocols are as fast as the classical protocol
and use $\tilde{O}(\log n)$ random bits in total, in contrast to $O(n\log^2n)$
random bits used in the well-known rumor spreading push protocol. These results
together give us almost full understanding of the randomness requirement for
this basic epidemic process.
  Our protocols rely on a novel reduction between rumor spreading processes and
branching programs, and this reduction provides a general framework to
derandomize these complex and distributed epidemic processes. Interestingly,
one cannot simply apply PRGs for branching programs as rumor spreading process
is not characterized by small-space computation. Our protocols require the
composition of several pseudorandom objects, e.g. pseudorandom generators, and
pairwise independent generators. Besides designing rumor spreading protocols,
the techniques developed here may have applications in studying the randomness
complexity of distributed algorithms.
