Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOGSPACE ENCODABLE/DECODABLE CODES:
Reports tagged with logspace encodable/decodable codes:
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