Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > YAO'S XOR-LEMMA:
Reports tagged with Yao's XOR-lemma:
TR01-009 | 5th January 2001
Ronen Shaltiel

#### Towards proving strong direct product theorems

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

TR20-094 | 24th June 2020
Ronen Shaltiel

#### Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

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

ISSN 1433-8092 | Imprint