Venkatesan Guruswami, Valentine Kabanets

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 >>>