We prove a version of the derandomized Direct Product Lemma for
deterministic space-bounded algorithms. Suppose a Boolean function
g:\{0,1\}^n\to\{0,1\} cannot be computed on more than 1-\delta
fraction of inputs by any deterministic time T and space S
algorithm, where \delta\leq 1/t for some t. Then, for t-step
walks w=(v_1,\dots, v_t) ... more >>>