A fundamental question of complexity theory is the direct product
question. Namely weather the assumption that a function $f$ is hard on
average for some computational class (meaning that every algorithm from
the class has small advantage over random guessing when computing $f$)
entails that computing $f$ on ... more >>>

Yao's XOR lemma states that for every function $f:\set{0,1}^k \ar \set{0,1}$, if $f$ has hardness $2/3$ for $P/poly$ (meaning that for every circuit $C$ in $P/poly$, $\Pr[C(X)=f(X)] \le 2/3$ on a uniform input $X$), then the task of computing $f(X_1) \oplus \ldots \oplus f(X_t)$ for sufficiently large $t$ has hardness ... more >>>