Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNIFORM SPACE-EFFICIENT REDUCTIONS:
Reports tagged with uniform space-efficient reductions:
TR05-057 | 19th May 2005
Venkatesan Guruswami, Valentine Kabanets

Hardness amplification via space-efficient direct products

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




ISSN 1433-8092 | Imprint