The (easy direction) of Yao's minmax lemma says that if there is a
randomized algorithm A which solves some problem (meaning that for every
input, A succeeds with high probability) then there is a deterministic
algorithm B of "roughly the same complexity" that solves the problem
well on average (meaning that B succeeds with high probability on a
random input). This can be viewed as "weak derandomization" and the
statement follows by an averaging argument: there exist a fixed value r
for A's random coins such that hardwiring r into A produces the
deterministic algorithm B. Note that this averaging argument does not
provide an explicit way to find r.

Recently, Zimand (building on an approach by Goldreich and Wigderson)
proved an explicit version of the implication for randomized decision
trees which toss ``few'' random coins. In this work, we consider weak
derandomization of various classes of randomized algorithms.

We develop a new proof technique that applies to any class of randomized algorithms as long as one can explicitly construct an appropriate randomness extractor. Using this approach we prove unconditional weak derandomization results for communication games, constant depth circuits and streaming algorithms. More precisely we show that:

1. Given a randomized communication protocol that tosses few random
coins and assuming that this protocol is explicitly constructible (in
the sense that players can compute their strategy in polynomial time).
Then, there is an explicitly constructible deterministic communication
protocol of comparable communication complexity that simulates the
randomized protocol correctly on most inputs.

2. Given a randomized algorithm that can be implemented by a uniform
family of poly-size constant depth circuits we construct a uniform
family of deterministic poly-size constant depth circuits that succeed
on most inputs. (A classic result by Nisan and Wigderson gives a
deterministic circuit that succeeds on all inputs but has
quasi-polynomial size).

Our techniques follow the approach of Goldreich and Wigderson in the
sense that we also ``extract randomness from the input''. However, in
contrast to previous papers we use seedless extractors rather than
seeded ones. We use extractors for bit-fixing sources (for decision
trees) 2-source extractors (for communication games and streaming
algorithms) and PRG based extractors (for constant depth circuits).