Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AVERAGE-CASE HARD:
Reports tagged with average-case hard:
TR07-130 | 3rd December 2007
Ronen Shaltiel, Emanuele Viola

#### Hardness amplification proofs require majority

Hardness amplification is the fundamental task of
converting a $\delta$-hard function $f : {0,1}^n -> {0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,
where $f$ is $\gamma$-hard if small circuits fail to
compute $f$ on at least a $\gamma$ fraction of the
inputs. Typically, $\eps,\delta$ are small (and
$\delta=2^{-k}$ captures the case ... more >>>

ISSN 1433-8092 | Imprint